アルゴリズムと計算量：解説つき練習問題

1計算量が測るもの

アルゴリズムは、問題を解く、正確な手順の有限なリストです。たとえばリストの並べ替えや、電話帳から名前を探すことなどです。

2 つのアルゴリズムが同じ問題を解いても、かかる時間が大きく違うことがあります。計算量は、入力が大きくなると仕事の量がどのように増えるかを表します。

入力の大きさを n と呼びます：並べ替える項目の数、リストの長さ、グラフの節点の数などです。

1000 ページの電話帳から名前を探す場合を考えましょう。すべてのページを読むと、最大 1000 ステップかかります。真ん中を開いて毎回半分にしていくと、約 10 ステップですみます。

時間計算量はステップ数を数えます。空間計算量は追加のメモリを数えます。どちらも n の関数として書きます。

通常は最悪の場合、つまり大きさ n のすべての入力のうち最も仕事が多い場合を見ます。ときには、平均の場合や最良の場合が問われることもあります。

2ビッグオーと増加の階級

ビッグオー記法は、大きな n で重要なものだけを残します。定数倍を捨て、最も速く増える項だけを残します。

n = 1000 のとき、n² の項は 3 000 000 ですが、5n は 5000 にすぎません。小さい項は合計をほとんど変えません。

次の階級が何度も出てきます。増加が遅いものから速いものの順です：

• O(1)（定数）：添字で配列の要素を読む。
• O(log n)（対数）：二分探索。毎回、問題を半分にします。
• O(n)（線形）：すべての項目を 1 回走査する。たとえば最大値を見つける。
• O(n log n)：マージソートのような優れた並べ替えアルゴリズム。
• O(n²)（2 次）：項目に対する二重ループ。たとえばバブルソート。
• O(2ⁿ)（指数）：すべての部分集合を試す。すぐに実用にならなくなります。

ビッグオーは上界です：仕事量は多くともこの速さでしか増えません。Ω（ビッグオメガ）は下界、Θ（シータ）は上界であり下界でもある厳密な界です。

ビッグオーでは、対数の底は関係ありません。底が異なる対数は、定数倍しか違わないからです。

3探索、整列、再帰

ほとんどすべての講義に出てくるアルゴリズムがいくつかあります。その計算量は事実として覚えましょう。

• 線形探索は項目を 1 つずつ調べます：O(n)。二分探索は整列済みの配列が必要で、毎回範囲を半分にします：O(log n)。
• バブルソート、挿入ソート、選択ソートは、二重ループで項目を比較して入れ替えます：O(n²)。挿入ソートは、すでに整列済みの配列では O(n) です。
• マージソートは配列を半分に分け、それぞれを整列して併合します：どの場合でも O(n log n) で、追加メモリは O(n) です。
• クイックソートはピボットを中心に分けます：平均では O(n log n) ですが、最悪の場合は O(n²) です。たとえば、整列済みの配列で先頭要素をピボットにした場合です。
• 項目を比較するだけの整列では、最悪の場合に Ω(n log n) より速くはできません。計数ソートは比較をしないので、それより速くなります。

再帰関数は、より小さい入力で自分自身を呼び出し、直接答えられる基底ケースに達するまで続けます。その実行時間は漸化式で書きます：

• T(n) = T(n/2) + O(1) は、二分探索と同じく O(log n) になります。
• T(n) = 2T(n/2) + O(n) は、マージソートと同じく O(n log n) になります。
• T(n) = T(n − 1) + O(n) は O(n²) になります。
• T(n) = 2T(n − 1) + O(1) は O(2ⁿ) になります。

知っておくべき設計の考え方が 3 つあります。分割統治法は、分割し、解き、併合します。貪欲法は、各ステップで局所的に最良の選択をします。動的計画法は、重なり合う部分問題の答えを記憶し、1 回だけ計算します。

4ステップごとの方法

コードの時間計算量を求めるには：

1. n が何かを決めます：入力の大きさです。
2. 各ループが何回実行されるかを数えます。毎回 1 ずつ増えるループは約 n 回実行されます。2 倍にする、または半分にするループは約 log₂ n 回実行されます。
3. 入れ子になったループは掛け算になります。順に続くループは足し算になります。
4. 再帰関数では、漸化式を書きます：何回の呼び出しが、どの大きさで行われるか、さらに 1 回の呼び出しあたりの仕事量です。
5. 最も速く増える項を残し、定数を捨てます。
6. 小さな数で確認します。たとえば n = 8 や n = 1024 です。

理論の問題では、まずそれが述べているアルゴリズムや考え方の名前を挙げ、次にその計算量と条件（整列済みの入力、非負の重み、重なり合う部分問題）を思い出します。

5例題

すべてのステップをたどりましょう。開く前に次のステップを予想してみましょう。

6よくある間違い

• 順に続くループを掛け算してしまう。n + n = 2n でも O(n) のままです。
• O(2n) や O(n/2) のように、定数を残す。どちらも O(n) です。
• 倍々になるループを n 回と数える。実際には約 log₂ n 回実行されます。
• 整列されていないデータや、中央に 1 ステップで到達できない連結リストで、二分探索を使う。
• 最悪の場合を問われているのに、クイックソートの平均の場合を答える。
• ビッグオーが「ちょうど」を意味すると考える。O(n²) は上界で、Θ(n²) が正確な増加の仕方です。

7試験問題の例

• やさしい：用語と事実。二分探索、マージソート、配列アクセスの計算量、O、Ω、Θ の意味、再帰とは何か。
• ふつう：概念の応用。コード片の計算量、解くべき漸化式、n が 2 倍になったときの時間の変化、課題に合うアルゴリズム。
• むずかしい：事例と分析。マスター定理、クイックソートの最悪の場合、貪欲法と動的計画法の比較、クラス P、NP、NP 完全。

P には、多項式時間で解ける問題が含まれます。NP には、解を多項式時間で検証できる問題が含まれます。P の問題はすべて NP にも含まれます。P = NP かどうかは、まだわかっていません。