英語の勉強にMITの講義でも Lec 6 | Introduction to Algorithms(SMA 5503)
またタイトル変えましたが気にせず、6回目の講義を聞いていきます。
シラバスとか。
Introduction to Algorithms (SMA 5503) | Electrical Engineering and Computer Science | MIT OpenCourseWare
Today we're going to not talk about sorting.
・・・ザワザワ・・・な、何だって・・・
- 文法的にnotの位置が気になる。
- そう言えば、英語の勉強なので、調べます。
- 教科書的にはto不定詞の否定はnot to do 〜。to not do 〜もかなり一般的。
- だけど、be going to do 〜だから・・・be not going to do 〜となるはずだが、否定する所が遠い。
- 結論:言いたい部分だけ否定するなら、be going to not do 〜はアリかな。
Order statics
- ん? sortingじゃね?
- ナイーブな実装なら、ソートして、n th の位置を持ってくるよね。
- 一般的にO(n log n)な気がする。
- 調べる。
- Order statistic - Wikipedia, the free encyclopedia
- 「これは使えそうだ」
- 検索で上位何件を引っ張ってこれそうな気がする。
- だけどやっぱり統計勉強しないといけないわけで(涙)
- とりあえず、高校の参考書からかな。
- だいぶ間が開いたけど、ちょっと再開。←使い回し。
- この辺りも。選択アルゴリズム - Wikipedia
- Randomized divide and conquer
- うぅん全然わからんな。今度聞いてみよう(汗
- 難しく考えていたけど、最小、最大を取り出すのは簡単。O(n)
- そこで思いついたナイーブな実装2は、ソートする対象はk番目の要素までとすると・・・
- kが小さければだいぶ早いけど、O(n log k)かかる。
単語
- order n
- the way in which people or things are placed or arranged in relation to each other