Algorithms part1のつづき(search)

時間がかかりながらも、stanford大のAlgorithms part1の講義を視聴している。

merge+sortのアルゴリズムを例として、アルゴリズムの処理量（オーダー）について考える。
処理するデータがn個あったとき、そのアルゴリズムは
nに比例して処理量が増えるのか（つまりO(n)）、はたまたO(log2n)なのか、などを見積もる。

処理量の見積もりの話の流れから、searchアルゴリズムが出てきた。
ソートは使うことは別に想定されてないみたいだったけど、ちょっと書いてみるかと思って、 自分でsearchで有名な二分木を再帰で書いてみたけど、これまた時間かかった・・・
おそらく、すぐにコーディングを始めるのがよくない。
紙に書いて分岐など整理してから取りかかるようにしよう。その昔、先生に言われたかも。
例によって、コードを晒してみる。


sortもだけど、searchも、Pythonビルドインの関数は自分の関数と比べてみると恐ろしく速い。
どうやってるのかしら。