英語の勉強にMITの授業でも Lec 1 | MIT 6.046J / 18.410J Introduction to Algorithms
アルゴリズムの授業をダラダラ聞いてみる。
字幕付いてるので聞き取れなくても安心。
- 最初の方は授業の進め方。
- 飛ばしていいと思うが、耳慣らし。
- パフォーマンスより重要なことは?
- ひみつ
- sortingのお話。
- 定番ネタ。
- わかりやす!!
- Insertion sort 挿入ソート。
- 段々本題のanalysisの方へ。
- 早速深い底へ降りた。流石MITデス。
- BIG IDEA!
- 数学的に落としこむ。
- 数学は時間を無視出来るのに、計算量って意外と矛盾してる側面がある気がする。for what?
- この辺のさわり。asymptotic notication→Big O notation - Wikipedia
- merge sort
- シンプル!!
- 半分に分けて、一つのリストにまとめていく。
- 再帰をanalysis
- この辺思い出した。ヒープソート - ボクノス
- Haskellの実装がオモロイな。マージソート - Wikipedia 全部分割された状態から始めれば、リストを半分にする手間がイラナイ。なるほど!!
- 以下考察
- 計算量は、T(n) = 分割O(T(n)x2) + 結合にO(n)、葉がO(1)。再帰。
- 正確に計算量を求めるとn * log_2(n) + n回。
- リストの結合にかかるコストは、どのレベルでも変わらないので、横列はn回。
- 葉の部分を除いた高さは、n = 2^h。h = log_2(n)。
- 葉の部分は含まれてないので+n回。
- 漸化式の一般項を求めるとかやった気がする。スキル不足を感じました。
- 次回が楽しみ。
単語
忘れてたけど英語の勉強ね。OALD,LDOCE,genius辺りから。
- assumption n.
- a belief or feeling that sth is true or that sth will happen, although there is no proof 当然のことと考えること
- bogus adj.
- pretending to be real or genuine いんちきの
- asymptote n.
- a straight line approached by a given curve as one of the variables in the equation of the curve approaches infinity. 漸近線 asymptoticは形
- moderately adv.
- to an average extent; fairly but not very 多くもなく、少なくもなく。
- sloppy adj.
- that shows a lack of care, thought or effort
雑感
まとめ
教えてる内容は普通でしたが、アプローチによってこんなに授業が変わるのかと感動しました。I was moved!