1つの問題にたくさんのアルゴリズム
アルゴリズムとは、問題を解くための決まった手順のことです。たいていの問題は、2つ以上のアルゴリズムで解けます。たとえばリストから名前を探すとき、全部の名前を順に確かめることもできますし、リストが並んでいれば、半分ずつに絞っていくこともできます。
どちらも正しい答えが出ます。違うのは効率、つまりどれだけ手間とメモリが必要かです。データが大きくなっても速いままのアルゴリズムを選ぶのが、よいプログラマーです。
かかる時間で比べるには
ストップウォッチで測るのは公平ではありません。速いパソコンなら、遅いアルゴリズムでも速く見えてしまうからです。そこで、入力の大きさ n に対して、比較・入れ替え・足し算などの基本的な手数を数えます。
最良・平均・最悪のケース
最良のケースは、いちばん運のよい入力です（13が最初の箱にある：1手）。最悪のケースは、いちばん運の悪い入力です（13がない：n手）。ふつうは最悪のケースを使います。それは「どんなときでもこれより遅くならない」という約束になるからです。
時間計算量と空間計算量
時間計算量は、n が増えたときに手数がどう増えるかを表します。空間計算量は、n が増えたときに追加のメモリがどう増えるかを表します。マージソートは速いですが追加のメモリが必要です。バブルソートは追加のメモリがほとんどいりませんが、遅いです。
ビッグO記法
ビッグOは、細かい部分を無視して、増え方だけを表します。いちばん大きい項だけを残し、定数は捨てます。3n² + 5n + 2 は O(n²) になります。n が大きいとき、n² の部分がほぼ全部を占めるからです。
| ビッグO | 名前 | n = 16 | n = 1000 | 例 |
|---|---|---|---|---|
| O(1) | 定数 | 1 | 1 | 配列の5番目の要素を読む |
| O(log n) | 対数 | 4 | 約10 | 二分探索 |
| O(n) | 線形 | 16 | 1000 | 線形探索、最大値を探す |
| O(n log n) | n log n | 64 | 約10,000 | マージソート |
| O(n²) | 2乗 | 256 | 1,000,000 | バブルソート、二重ループ |
コードを見るときの目安：n個を1回まわるループはO(n)、ループの中にループがあればO(n²)、毎回問題を半分にするならO(log n)です。
線形探索と二分探索の効率
線形探索は、要素を1つずつ調べます。最悪の場合は n 回の比較なので O(n) です。並んでいてもいなくても、どんなリストにも使えます。
二分探索は、並んだリストが必要です。真ん中を見て、それが大きすぎれば右半分を捨て、そうでなければ左半分を捨てます。1手ごとにリストが半分になるので、最悪の場合は約 log₂ n + 1 回の比較、つまり O(log n) です。100万個なら、100万回ではなく約20回ですみます。
並べ替えアルゴリズムの効率
バブルソート、挿入ソート、選択ソートは、ループの中にループがあるので、比較は約 n²/2 回、つまり O(n²) です。挿入ソートは、すでに並んでいるリストなら最良のケースで O(n) になります。
マージソートは、リストを約 log₂ n 回半分にし、各段階で約 n の仕事をします。だから O(n log n) です。追加で O(n) のメモリが必要です。
二分探索には並んだリストが必要です。探すのが1回だけなら、先に並べ替える（n log n）ほうが、線形探索1回（n）より手間がかかります。何回も探すなら、1回並べておく価値があります。
事前条件・事後条件と再帰の落とし穴
事前条件とは、アルゴリズムが始まる前に成り立っていなければならないことです（二分探索なら、リストが並んでいること）。事後条件とは、終わったときに保証されることです（並べ替えなら、どの要素も次の要素以下になっていること）。これを書いておくと、アルゴリズムのテストや証明がしやすくなります。
再帰とは、関数が、より小さい問題に対して自分自身を呼び出すことです。よくある間違いは次のとおりです。
- 終了条件（ベースケース）がない、または一度もたどり着かない：呼び出しが止まらなくなります（スタックオーバーフロー）。
- 呼び出すたびに問題が小さくなっていない。
- 同じ計算をくり返す：単純な再帰のフィボナッチは fib(3) を何度も計算し直すので、O(2ⁿ) のように増えます。答えを記録しておく（メモ化）と O(n) になります。
- とても深い再帰は、呼び出し1回ごとにスタックフレームを1つ使うので、メモリをたくさん使います。
やってみよう：2つの探し方で競争
1から32までの数字を紙のカードに書き、順番に伏せて並べます。友だちに秘密の数を1つ選んでもらいます。まず1枚ずつめくって、めくった枚数を数えます。次に、いつも真ん中のカードをめくって探します。これを5回くり返しましょう。6回より多くめくらずにすんだのはどちらの方法でしょう。最後の3Dステップのスライダーで確かめてみましょう（n = 32 のとき log₂ 32 = 5）。
重要な公式と用語
- 線形探索：最悪の場合 n 回の比較 → O(n)
- 二分探索：最悪の場合 約 log₂ n + 1 回の比較 → O(log n)
- バブル／挿入／選択ソート：約 n(n − 1)/2 回の比較 → O(n²)
- マージソート：約 n log₂ n 回の比較 → O(n log n)
- ビッグOのルール：いちばん大きい項だけ残し、定数は捨てる（5n² + 3n → O(n²)）
- n を2倍にすると：O(1) は同じ、O(log n) は +1、O(n) は ×2、O(n²) は ×4
例題
1. リストに名前が50個あります。線形探索の比較回数は、最良と最悪のケースでそれぞれ何回ですか。
最良のケース：名前が最初にある → 比較1回。最悪のケース：名前が最後にある、またはない → 比較50回。線形探索は O(n) です。
2. 並んだ1024個のリストで、二分探索が必要とする比較は最大で何回ですか。
1手ごとに半分になります：1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1。半分にするのが10回で、最後の確認を足して、最大11回の比較です（log₂ 1024 = 10）。
3. f(n) = 4n² + 10n + 7 のビッグOを答えましょう。
いちばん大きい項（4n²）を残し、定数の4を捨てて、O(n²) です。
4. i を1から n まで動かすループがあり、その中で j を1から n まで動かすループがあります。内側の行は何回実行されますか。
i の n 個の値のそれぞれについて n 回なので、n × n = n² 回です。時間計算量は O(n²) です。
5. O(n²) のプログラムが1000個の並べ替えに2秒かかります。3000個ならおよそ何秒かかりますか。
n が3倍になるので、n² は 3² = 9 倍になります。約 2 × 9 = 18 秒です。
6. n = 1000 個のとき、バブルソートとマージソートを比べましょう。
バブルソート：約 n²/2 = 500,000 回の比較。マージソート：約 n log₂ n = 1000 × 10 = 10,000 回。マージソートの仕事量は約50分の1ですが、追加のメモリが必要です。
よくある間違い
- 1台のパソコンのストップウォッチだけで速さを測ること。代わりに、n に対する手数を数えましょう。
- 並んでいないリストに二分探索を使うこと。二分探索の事前条件は、リストが並んでいることです。
- ビッグOに定数を残すこと。たとえば O(2n) と書くのは間違いで、O(n) です。
- ベースケースのない再帰関数や、問題が小さくならない再帰関数を書くこと。