🗺️ アルゴリズムクエスト
STAGE 9 ― 計算量で選ぶ ―
クリア 0 / 9
🧭 地図
STAGE 9

計算量で選ぶ

速いアルゴリズムの見つけ方
🎯 ミッション
計算量の違いがデータの数でどれほど効くかと、速いアルゴリズムを作る考え方を説明できるようになろう。確認クイズに全問正解すれば合格。
未達成
ねこ博士
最後のステージは、ここまでの旅のまとめだ。1つ目のステージで、アルゴリズムの速さを「N が増えたときの手間の増え方」で比べると決めたね。ここまでに出てきたものを、計算量の小さい順に並べてごらん。
うさ美
ハッシュ表で探すのが平均 O(1)、二分探索が O(log N)、線形探索が O(N)、クイックソートが平均 O(N log N)、バブルソートが O(N²)。素朴な再帰の階段の計算は、n が1増えるごとに1.6倍くらいになったので、指数のように増える型でした。
ねこ博士
N が100万になると、O(N log N) なら一瞬で終わる仕事が、O(N²) では何十分もかかり、指数の型では宇宙の年齢でも足りない。アルゴリズムを変えることは、コンピュータを何万倍も速くすることより効くことがあるんだ。
うさ美
速いアルゴリズムは、どうやって見つければいいんですか? 毎回ひらめくしかないんでしょうか。
ねこ博士
ひらめきに頼らないための、よく効く考え方が3つある。ここまでの旅を思い出しながら整理しよう。
① 捨てる:1回の比較で、答えが無いと分かった部分をまとめて捨てる(二分探索は半分を捨てた) ② 分ける:問題を小さい問題に分け、それぞれを同じやり方で解いてから組み合わせる(クイックソート・マージソート。分割統治と呼ぶ) ③ 覚える:一度計算した答えを書いておき、同じ計算をくり返さない(動的計画法・ダイクストラ法の確定した距離)
うさ美
もう1つ、ハッシュ表やキューのように、データの置き方を変えるだけで速くなるものもありました。
ねこ博士
そう。データをどんな形でしまっておくかをデータ構造と呼ぶ。配列、連結リスト、ハッシュ表、キュー、スタック、優先度付きキュー。同じ「探す」でも、データ構造によって得意・不得意が違った。
並んだ配列:何番目にもすぐ行ける。二分探索 O(log N)。途中に入れるのは O(N) 連結リスト:途中に入れる・外すのは O(1)(場所が分かっていれば)。何番目かへ行くのは O(N) ハッシュ表:ぴったり一致を探す・入れるのは平均 O(1)。順番や範囲は苦手 キュー・スタック:入れた順・逆順に取り出すのは O(1) 優先度付きキュー:いちばん小さいものを取り出すのが O(log N)
うさ美
アルゴリズムとデータ構造は、セットで選ぶものなんですね。
ねこ博士
そう。それから、計算量にはもう1つ、どれだけメモリを使うか(空間計算量)もある。動的計画法は、表のぶんだけメモリを使って、時間を買っていた。時間とメモリの取り引きも、選ぶときの大事な物差しだ。
うさ美
村長の名簿の問題は、どう答えればいいでしょう。
ねこ博士
100万人の名簿から名前で探すなら、ハッシュ表で平均 O(1)。五十音順の一覧も必要なら、並んだ配列を二分探索で O(log N)、人が増えるたびに入れるのが大変なら、もっと工夫したデータ構造(木の形にしたものなど)を使う。何をしたいかで、選ぶものが変わるんだ。この旅の道具で、もうその判断ができるはずだよ。

確認クイズ

Q1. N = 100万のとき、手間がいちばん小さいのは?

Q2. 二分探索の速さの秘密を、3つの考え方で言うと?

Q3. 動的計画法について正しいのは?

← 前のステージ