コース 4

アルゴリズムのかたち

同じ問題にも、速い手順と遅い手順がある

さがす、ならべる、おぼえておく。手順の「かたち」が変わると、同じ仕事が千倍速くなることがあります。回数を数えながら、その理由を体で確かめます。

01 手順ということばあなたはすでに、速い手順をいくつも知っている。アルゴリズムという考え方と、「くらべた回数」という物差し。
02 さがす——まっすぐにいちばん素朴なさがし方「先頭から1つずつ」。最良の場合、最悪の場合、そして「ない」と言い切ることの値段。
03 さがす——半分に切るそろった数列なら、まんなかを1回見るだけで半分を捨てられる。二分探索のおどろくべき速さと、その速さを支えている「前提」の話。
04 ならべる——差しこみであなたがトランプで無意識にやっていた手順に、名前がつく。挿入ソートと、そろい済みなら5回・逆順なら15回という落差のはなし。
05 分けて、たばねるならべる前に、半分に分ける。マージソートという発想の転換と、コース2で出会った「再帰」との再会。速さの代金も正直に。
06 速い・遅いには、かたちがある長さを倍にしながら測りなおすと、バラバラだった回数が法則になる。対数・比例・n log n・総当たり——成長のかたちに名前を与える。
07 おぼえておくという工夫同じ計算を、二度しない。一度出した答えを「おぼえておく」だけで、270万回の爆発が59回の直線に変わる——メモ化と、時間と空間のトレードオフ。
08 かたちを、選ぶ最終レッスン。「最強のアルゴリズム」は存在しない——量・回数・置き場の3つを聞けば、状況が手順を選んでくれる。