アルゴリズムの解析
アルゴリズムをただ書き下して「見よ！」というだけでは不十分で、アルゴリズムがすべきことを効率良く行うことを聴衆 (および自分自身) に納得させなければなりません。
正しさ
アプリケーションが置かれる環境によっては、プログラムが「常識的な」入力の全てに対してほとんどの場合に正しく動けばそれで OK とされることもあります。しかし、この本では違います。アルゴリズムは全ての可能な入力に対して常に正しいことを要求されます。加えて、アルゴリズムが正しいことは証明されなければなりません。直感に頼ったり、テストケースをいくつか通すだけでは不十分です。
講義の前半で見るアルゴリズムについては正しさが本当に明らかなことがありますが、「明らかである」が「間違っている」の同義語であることが本当によくあります。この講義で扱うアルゴリズムのほとんどは正しさの証明に苦労が伴います。なお正しさの証明には帰納法をよく使います。私たちは帰納法が大好きです。帰納法は友達です1。
もちろん、きちんとした証明を行うには、その前にアルゴリズムが何をするのかをきちんと説明しておく必要があります！
実行時間
同じ問題に対する異なるアルゴリズムをランク付けする最も一般的な方法は、どれだけ速く実行できるかで並べるというものです。理想的には、どんな問題に対しても可能なもののうち一番早いアルゴリズムが望まれます。アプリケーションが置かれる環境によっては全ての「常識的な」入力に対してほとんどの場合に速く動けばそれで OK ということもありますが、この本では違います。アルゴリズムはワーストケースにおいても常に効率良く実行できることが求められます。
実行時間をどうやって測るべきでしょうか？ 例えば \(\textsc{BottlesOfBeer}(n)\) を歌うにはどれだけの時間がかかるでしょうか？ 実行時間が入力 \(n\) の関数であることは明らかですが、実行時間は歌を歌う速さにも依存しています。バースを歌うのに 10 秒かける歌手もいますし、20 秒かける歌手もいるでしょう。技術を使うとさらに極端なことができます: モールス信号を使ってテレグラフで歌を書き留めたらバースにまる一分かかるでしょう。あるいはウェブから mp3 をダウンロードするならバースあたり十分の一秒で済みますし、 mp3 をコンピューターのメインメモリ上で複製するのはバースあたり数マイクロ秒しかかかりません。
このような場合に重要となるのは、\(n\) が大きくなるにつれて歌うのにかかる時間が時間がどう変化するかです。\(\textsc{BottlesOfBeer}(2n)\) を歌うには \(\textsc{BottlesOfBeer}(n)\) を歌うときの 2 倍の時間がかかり、この事実は技術と関係がありません。歌唱時間の漸近表記 \(\Theta(n)\) はこれを意味しています。
アルゴリズムの実行時間を調べるときには、アルゴリズムがある命令を何回実行するか、あるいはコード中のある場所に処理が何回到達するかを測定します。例えば "beer" という単語は \(\textsc{BottlesOfBeer}\) のバースにつき 3 回出てくるので、"beer" と何回歌ったかは歌唱時間の良い指標となります。この問題に対しては正確な答えが求まります: \(\textsc{BottlesOfBeer}(n)\) を歌うと "beer" はちょうど \(3n + 3\) 回歌われます。
ちょうどよいので触れておくと、多項式時間の歌唱時間を持つ歌はたくさんあります。次に示すのはほとんどの英語話者になじみのある歌です:
procedure \(\texttt{NDaysOfChristmas}\)(\(\mathit{gifts}[2..n]\))
for \(i \leftarrow 1\) to \(n\) do
"On the \(i\)th day of Christmas, my true love gave to me" と歌う
for \(j \leftarrow i\) downto 2 do
"\(j\) \(\mathit{gifts}[j]\)," と歌う
if \(i > 1\) then
"and" と歌う
"a partridge in a pear tree." と歌う
\(\textsc{NDaysOfChristmas}\) の入力は \(n-1\) 個のプレゼントが入ったリストであり、ここでは配列として表されます。歌唱時間が \(\Theta(n^2)\) であることを示すのは簡単です。正確に言うとプレゼントの名前はちょうど \(\sum_{i=1}^{n} i = n(n+1)/2\) 回歌われます (partridge in a pear tree を含む)。またクリスマスの最初の \(n\) 日で my true love がちょうど \(\sum_{i=1}^{n} \sum_{j=1}^{n} j\ =\) \(n(n+1)(n+2)/6\ =\) \(\Theta(n^3)\) 個のプレゼントをくれるというのも簡単に示せます。
多項式歌唱時間の歌は他には "Old MacDonald Had a Farm", "There Was an Old Lady Who Swallowed a Fly", "Hole in the Bottom of the Sea", "Green Grow the Rushes O", "The Rattlin' Bog", "The Court Of King Caractacus", "The Barley-Mow", "If I Were Not Upon the Stage", "Star Trekkin'", "Ist das nicht ein Schnitzelbank?"2, "Il Pulcino Pio", "Minkurinn í hænsnakofanum", "Echad Mi Yodea", そして "\(T o\) \(\kappa o \kappa o \rho \acute{\alpha} \kappa \iota\)" があります。これ以上はお好きな保育園に聞いてください。
procedure \(\texttt{Alouette}\)(\(\mathit{lapart}[1..n]\))
Chantez « Alouette, gentille alouette, alouette, je te plumerai. »
pour tout \(i\) de \(1\) à n
\(\qquad\)Chantez « Je te plumerai \(\mathit{lapart}[i]\). Je te plumerai \(\mathit{lapart}[i]\). »
\(\qquad\)pour tout \(j\) de \(i\) à \(1\)
\(\qquad\)\(\qquad\)Chantez « Et \(\mathit{lapart}[j]\) ! Et \(\mathit{lapart}[j]\) ! »
\(\qquad\)Chantez « Alouette! Alouette! Aaaaaa... »
\(\qquad\)Chantez « Alouette, gentille allouette, alouette, je te plumerai. »
もっと奇妙な歌唱時間を持つ歌もあります。現代的な例は Guy Steele (ガイ・スティール) による "The TELNET Song" であり、この歌は最初の \(n\) 個のバースを歌うのに \(\Theta(2^{n})\) の時間がかかります (Steele は \(n=4\) を勧めています)。それからもちろん、終わらない歌もあります3。
"The TELNET song" を除くと、これまでに紹介した歌はどれも入れ子になった小さなプールで表現される反復アルゴリズムであり、実行 歌唱時間は入れ子になった和で求めることができます。これに対して、再帰的なアルゴリズムの実行時間は再帰方程式を使って表現した方が自然です。例えば農民の掛け算アルゴリズムは次のように表されました: \[ x \times y = \begin{cases} 0 & \text{if } x = 0 \\ \lfloor x / 2 \rfloor \times (y + y) & \text{if } x \text{ が偶数} \\ \lfloor x / 2 \rfloor \times (y + y) + y & \text{if } x \text{ が奇数} \\ \end{cases} \]
このアルゴリズムを使って \(x \cdot y\) を計算するのに必要なパリティ検査、足し算、mediation 演算の数を \(T(x, y)\) とすると、この関数は再帰的な不等式 \(T(x, y) \leq T(\lfloor x/2 \rfloor, 2y) + 2\) および基底ケース \(T(0, y) = 0\) を満たします。次の章で説明されるテクニックを使うと上界を求めることができ、\(T(x,y) = O(\log x)\) と分かります。
アルゴリズムの実行時間が、サブルーチンで利用されるデータ構造の実装に依存することもあります。例えば Huntington-Hill の配分アルゴリズム \(\textsc{ApportionCongress}\) の実行時間は \(O(N + RI + (R - n)E)\) と表すことができ、ここで \(N\) は \(\textsc{NewPriorityQueue}\) の実行時間、\(I\) は \(\textsc{Insert}\) の実行時間、\(E\) は \(\textsc{ExtractMax}\) の実行時間です。\(R \geq 2n\) という常識的な仮定 (どの州にも平均して二つの議席が割り当てられるという仮定) を置くと上界を \(O(N + R(I + E))\) と単純化でき、この実行時間は使用される優先度付きキューの実装に依存します。国勢調査局では優先度付きキューをソートされていない配列を使って実装するので \(N = 1 = \Theta(1)\) および \(E=\Theta(n)\) であり、\(\textsc{ApportionCongress}\) の実行時間は \(O(Rn)\) です。しかし二分ヒープまたはヒープで順序付けされた配列を使って優先度付きキューを実装すると \(N = \Theta(1)\) および \(I = E = O(\log n)\) となるので、アルゴリズム全体の実行時間は \(O(R \log n)\) となります。
最後に、アルゴリズムを解析する上で実行時間以外のリソース、例えば空間、コイン投げの回数、キャッシュのページフォルトの回数、プロセス間通信の数、my true love が私にくれるプレゼントの数、などが重要になることがあります。こういったリソースも実行時間を解析するのと同じテクニックを使って解析できます。例えば \(n\) 桁の整数の格子掛け算が消費する空間は、部分積を全て書き留めておくなら \(O(n^{2})\) であり、必要となるたびに計算するのであれば \(O(n)\) です。