英語の勉強にMITの授業でも Lec 4 | MIT 6.046J / 18.410J Introduction to Algorithms

English

今日もダラダラ英語頑張りますｗ

継続は力なり。

Quick sort

  • お、ようやく登場。期待です。
  • 今日はbald/bɔːld/な教授(発音が違ってた・・・)
  • Sort "in place"
    • 今までと形が違うのが特徴。
  • practical(with tuning)
    • また重要な発言。
  • Divideなが！！
    • 後はシンプル。
    • そういや１段階ごとにn - 1要素数が減るんだな。枝になればなるほど要素数が減る。これは非常に大きい？という考察。
  • ここからanalysis。
    • worst case
      • T(n) = T(0) + T(n - 1) + Θ(n)
      • Σが見える・・・あぁぁぁぁぁ・・・1個づつ並べてんじゃん！！
      • O(n^2)ですね。
      • 解説あり。とんくす。
    • best case
      • 半々ですな。
    • 1/10,9/10
      • 良い練習問題。
      • 間違ってもいいからvoteせよ。と。
    • 考察2
      • 再帰するごとにピポットが取り除かれ、葉になる。つまりwrostを厳密に計算すると(n^2) / 2 + n回。
      • bestの場合・・・n log_2 n + nよりは少ない・・・考え中。
        • 1, 3, 7, 15, 31, 63・・・でツリーが深くなる。ツリーの高さhの時の要素数は、Fn(h) = 2*Fn(h - 1) + 1 (h > 0), Fn(h) = 1 (h == 0)こんなもん。再帰を展開すると・・・考え中。
        • n log_2 nならば、1, 2, 4, 8, 16, 32・・・あ、一段減ってるだけ。展開してないけど、2^(h + 1) - 1。つまり、n回早くなっただけか。結合にnかかるから、n log_2 n。出た。
    • 再開。lucky, unluckyが交互に繰り返された場合。
      • 視点が面白い。
    • で、ソート済みだと遅いから、ビボットをランダムにｗ
      • するっと、最悪のケースはよーわからんｗｗｗ
      • で、それをanalysis。ってマジっすか。
      • その前にストレッチタイム入ります。
        • もうダメ・・・ツボった。アメリカ人自由過ぎるｗｗｗ
      • ほほぅぅぅ。なるほど。確率論で攻めればいい。
      • なるほどと思ったが、何言ってるかワカンネ。英語が理解できないのか数学が理解できないのかｗ
      • このへん→Quicksort - Wikipedia
        • 英語版のWikiは詳しすぎる。
    • 気付いたら寝てたぜｗｗ
      • 数学部分は理解度が落ちる。もう一回聞こう。

単語

一応英語の勉強なので。

practical /ˈpræktɪkəl/ adj
connected with real situations rather than with ideas or theories 実用的な
partition v
to divide sth into two parts 分割する
invariant adj
always the same; never changing
variant n, adj
a thing that is a slightly different form or type of sth
boundary n
a real or imagined line that marks the limits or edges of sth and separates it from other things or places; a dividing line
alternate n
happening or following one after the other regularly

まとめ

TTFN!

更新履歴

  • 2012/10/20
    • 続きを聞いた。