英語の勉強に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

更新履歴

進みが遅いので更新したらここに書いとく。

  • 2013/03/01
    • 微妙に進めた気がする。
  • 2013/01/28
    • シラバスとか追加した。
    • そういやデザイン変えた。