アルゴリズムと計算量

【1】整数の並び

【2】文字列の並び

まず、もっとも単純な整列アルゴリズムの1つである挿入ソートを紹介します（挿入ソートと同様のシンプルな整列アルゴリズムとして、バブルソートや選択ソートが知られています）。

このアルゴリズムによって整列する例を以下に示します。 入力の並びとして先程の例【1】の

を用います。

図の赤い縦線より左の薄い青の部分が整列済みの部分、右が未整列の部分です。各行では、1つ上の行で赤線のすぐ右にあった値を、整列済みの部分の適切な位置に挿入します（挿入した値を濃い青で、挿入位置を探すときに比較した値を太い枠で示しています）。

このように、挿入する値を、整列済みの部分の末尾から先頭に向かって順に比べ、自分以下の値が見つかったところで止まります。

比較回数が整列アルゴリズムの時間計算量を決定づけていますので、比較回数を数えることにします。計算量を考える場合は、一般に \(n\) 個の並びの中で、もっとも時間がかかる入力を与えた最悪のケースを考えます。\(k\) 回目の挿入では、整列済みの部分に \(k\) 個の値があり、最悪の場合はそのすべてと比較が必要になります。8個の並びでは挿入が7回あるので、最悪の比較回数は

となり、28回です。この入力例では実際の比較回数は図より

となり、22回で済んでいます。最後の行で右端の「3」を挿入するとき、すでに左側にあるもう1つの「3」と比べて「自分より大きくない」とわかった時点で止まるので、それより左の1や2とは比較しないことに注意してください。つまり、「9,7,6,4,3」の5つの値と比較するので、比較回数は5となります。

入力として与える値の並びの長さ（入力サイズ） \(n\) に対する最大の比較回数を \(T(n)\) とおくと、以下のようになります。

この式から、入力が大きくなったときに比較回数がどう増えるかを見てみましょう。

\(n\) が2倍になると比較回数はほぼ4倍、4倍になると約16倍、10倍になると約100倍です。これは \(T(n)\) の中で \(\frac12n^2\) の項が支配的だからです。\(n\) が大きいとき、\(\frac12n\) の項の影響は \(\frac12n^2\) に比べると微々たるものです。また、「2倍にすると4倍」という増え方は、係数が \(\frac12\) でも \(100\) でも変わりません。そこで、増え方だけに注目するときは、係数と小さい項を省いて \(T(n)=\text O(n^2)\) と書きます（「オー・エヌ二乗」と読みます）。この書き方の意味は、後の「時間計算量」の節で詳しく説明します。

挿入ソートのアルゴリズムのプログラム例が以下のコードです。あくまでも例示ですので、理解する必要はありません。このくらいのコード量で書けるということがわかれば大丈夫です。

このコードはプログラミング言語 Julia で記述してみました（なぜ Julia を用いたかというと、単に私が好きな言語だからです…）。

実際にこの手順で、挿入ソートが \(n\) 個の値を整列（ソート）するのに必要な比較回数（≒計算時間）を数えて、グラフにしてみました（本文のプログラムと同じ手順を実行して数えています）。

このグラフで、いちばん上の青い曲線は、

のように完全に降順に並んだ値の列を入力として与えた場合です。挿入ソートでは、このような入力が最悪の場合になります。この曲線は上で計算した \(T(n)=\frac12n^2-\frac12n\) と一致します。

いちばん下の、ほぼ水平にみえる緑の線は、もともと整列済みの

のような値の列を入力として与えた場合です。挿入ソートでは、このような入力が最良の場合となり、比較回数は \(n-1\) 回です。つまり、もっとも速く計算できる場合は、入力の値の数 \(n\) に比例する時間で済みます。この線がほぼ水平にみえるのは縦軸が最大50万回まであるためで、\(n=1{,}000\) でも999回しかありません。

真ん中のオレンジの点は、ランダムに並べ替えた値の列を入力として与えた場合の比較回数です。最悪の場合のおよそ半分の回数ですが、やはり放物線（2次関数のグラフ）の形に増えてゆくことがわかります。これが挿入ソートの平均的な計算量の様子です。

この整列（ソート）アルゴリズムは、値の性質としては大小比較しか用いていないことに注意してください。これ以外の情報を用いると計算量が変わってきます（後の「計数ソート」で扱います）。

挿入ソートと並んでよく引き合いに出される素朴な整列アルゴリズムに、選択ソートがあります。考え方はとても単純で、未整列の部分から毎回いちばん小さい値を選び、左から順に確定させていくだけです。

下の図では、各行で残りの中の最小値を赤い丸で示しています。その値は、次の行で整列済みの部分（水色）の右端の位置に移り、もともとそこにあった値と入れ替わります。たとえば1行目で選んだ1は先頭の9と、2行目で選んだ2は2番目の9と入れ替わります。

選択ソートでは、\(n\) 個から最小値を選ぶのに \(n-1\) 回、次に残りの \(n-1\) 個から選ぶのに \(n-2\) 回……と比較するので、比較回数は入力によらず常に

回です。挿入ソートは整列済みの入力なら \(n-1\) 回で済みましたが、選択ソートはどんな入力でも、最小値を探すために残りをすべて調べるので、常に \(n^2\) に比例する回数の比較をします（後で説明する記号を使うと \(\Theta(n^2)\) です）。一方、値の入れ替えは各段階で1回まで、全体で高々 \(n-1\) 回で済みます。

バブルソートは、隣り合う2つの値を比べて、左の方が大きければ入れ替える、という操作だけで整列します。

大きな値が、水の中の泡（バブル）が浮かび上がるように右へ移動してゆくことが名前の由来です。まず、1回目のパスの様子を見てみましょう。

1回目のパスでは7回の比較で、最大の9が右端まで移動しました。各パスの終わりの状態を並べると次のようになります。

パス5の後にはすでに整列が終わっていますが、アルゴリズムはそれを知らないので、パス6で入れ替えが起きないことを確かめてから終了します。比較回数は \(7+6+5+4+3+2=27\) 回でした。最悪の場合（降順に並んだ入力）には、パスが \(n-1\) 回必要で、比較回数は挿入ソートや選択ソートと同じ \(\frac{n(n-1)}2\) 回になります。整列済みの入力なら、1回目のパス（\(n-1\) 回の比較）で入れ替えが起きず、すぐに終了します。

バブルソートは仕組みが分かりやすい反面、入れ替えの回数が多く、実際のプログラムでは挿入ソートより遅いのが普通です。後のコラムで紹介するクイックソートの考案者ホーアも、最初に思いついたバブルソートを「遅そうだ」として退けています。

「並びの値からの情報として大小比較の結果しか用いない」という前提条件をなくすと、もっと速いアルゴリズムが作れるかもしれません。たとえば、並びの値の範囲があらかじめわかっていて、比較的狭い範囲であったとします。前の例 \(\langle 9,1,4,3,7,6,2,3\rangle\) をもう一度用いると、値の範囲が1から9までに限られるとして、それがあらかじめわかっていたとします。すると、次のような方法が考えられます。

すると、上図のように \((1,1,2,1,0,1,1,0,1)\) の並びが得られます。後は先頭から順番にカウントをみてゆき、カウントの数だけ、対応する値を出力すれば、整列完了です。

値の個数を \(n\)、値の範囲の広さ（箱の数）を \(k\) とします。入力を読む手間は \(n\) 個分、箱を初期化して順に調べる手間は \(k\) 個分、結果を書き出す手間は \(n\) 個分です。したがって、全体の時間計算量は

となります（「\(n+k\) に比例する」と読んでください）。この例では \((n,k)=(8,9)\) ですが、これはすべての操作がちょうど \(8+9=17\) 回で終わるという意味ではありません。範囲の広さ \(k\) も時間とメモリを左右する点が大切です。また、計数ソートは値どうしを一度も比較していないことにも注意してください。

値の範囲があらかじめわかっていても、たとえば、64ビットで表現できる整数の範囲となると、コンピューターの記憶装置を使い尽くしてしまいますし、膨大な時間がかかることになります。以下に計数ソートのプログラム例を掲載します（やはり Julia で記述してあります）。

計数ソートは非常に高速ですが、以下の制限があります。

このため、実際のプログラミングでは比較ベースの整列アルゴリズムが主流となっています。

ここで、多くの人がつまずくポイントを整理しておきます。「最悪計算量」と「O記法」は、どちらも計算量の話に出てくるためよく混同されますが、別の軸の概念です。

挿入ソートで確かめてみましょう。最悪計算量 \(\frac{n(n-1)}2\) という1つの関数を、\(\text O(n^2)\) とも \(\Omega(n^2)\) とも \(\Theta(n^2)\) とも評価できます。また、最良計算量 \(n-1\) を \(\text O(n)\) と、Oを使って評価することもできます。

これで、計算量を議論するための指標である最悪計算量とビッグオー表記について準備ができました。

次に知っておく必要があるのは、ビッグオー表記による計算量の目安です。以下にビッグオー表記の関数を増加率の小さい順に並べます（ここでは、上界を用います）。これは増え方を比較する目安です。あるアルゴリズムの上界だけで、その問題を解くすべての方法の限界まで決まるわけではありません。

つまり、関数の増え方には次のような順序があります（\(\ll\) は「右の方が圧倒的に速く増える」という意味です）。

グラフの左上にある「1e3」「1e6」「1e18」は、縦軸の目盛りをそれぞれ \(10^3\)、\(10^6\)、\(10^{18}\) 倍して読むという意味です。ぜひ、Excel等のグラフ描画ツールによって実際に上記の関数のグラフを自分で描いてみて、この順序を実感してみてください。

8個の数値 \(\langle 9,1,4,3,7,6,2,3\rangle\) で具体的に見てみましょう。まず基準値を1つ選びます（ここでは説明のため「6」とします。基準値の選び方は後で述べるように性能に影響します）。基準値と比べて、6より小さいグループと6より大きいグループに振り分けます。基準値と等しい値が現れた場合は、基準値と一緒にその位置で確定させます。つまり「基準値より小さい」「基準値と等しい」「基準値より大きい」の3つに分割します。各グループの中では、元の並びの順序を保つことにします。

あとは、左右のグループそれぞれに同じ操作（基準値を選んで分割する）を、グループの要素が1個以下になるまで繰り返すだけです。この分割の繰り返しを木の形で表すと、次のようになります。

各段階での配列の状態をまとめると、次の表のようになります。

各段階での比較回数を数えると、次のようになります。

ここでは、2つの値の大小・等しさを一度で判定する比較を1回と数えて、合計13回です。< と == を別々に評価する実装では、その評価回数は増えます。比較回数を別のアルゴリズムやプログラムと比べるときは、何を1回と数えるかをそろえましょう。

理想的には、基準値が配列をほぼ半分に分けてくれます。すると分割の深さは \(\log_2 n\) 段ほどで、各段で全体をひととおり比較するので約 \(n\) 回、あわせて \(\text O(n\log n)\) になります（下図の左）。これは均等に分割できる場合の説明です。ランダムな基準値を使う場合の期待計算量も同じ評価になりますが、その証明には分割の確率を考える必要があります。

一方、毎回いちばん小さい（または大きい）値を基準値に選んでしまうと、グループが1個ずつしか減らず、深さが \(n\) 段になってしまいます（下図の右）。たとえば、すでに昇順に整列済みの \(\langle 1,2,\ldots,n\rangle\) に対して、いつも先頭を基準値にすると、この最悪の状況が起こります。このときの比較回数は

となり、挿入ソートの最悪の場合と変わらなくなってしまいます。挿入ソートにとっては最良だった整列済みの入力が、この選び方のクイックソートにとっては最悪の入力になるわけです。

値がすべて異なる場合、基準値を一様ランダムに選べば、どの入力に対しても期待時間は \(\text O(n\log n)\) です。3つの値の中央値を使う方法もよく用いられますが、それだけで最悪時間の保証が変わるわけではありません。同じ値が多い入力には、等しい値をまとめる3分割などの工夫が有効です。また、要素数の少ない部分配列では挿入ソートに切り替えると、さらに速くなります。クイックソートが広く使われているのは、平均的にはこの \(\text O(n\log n)\) が達成でき、しかも係数が小さく（実際に速く）、元の配列の中で並べ替える実装ができる（ただし、再帰の管理には追加のメモリを使う）からです。

下に Julia によるクイックソートのプログラムを載せておきます。この例は左右の配列を新しく作るので、元の配列内で並べ替える省メモリの実装とは異なります。アルゴリズムが単純なので（細かい効率を気にしなければ）、すぐに書き下せます（簡単のため、基準値と等しい値を左のグループに入れる2分割版にしてあります。この版では、すべての値が等しい入力で比較回数が \(n^2\) に比例してしまいます）。

標準ライブラリでは、用途や実装に応じてさまざまな整列法が使われています。関数名だけからアルゴリズムが決まるとは限りません。

「もっと速いアルゴリズムがあるかもしれない」という疑問に答えるため、理論的な限界を証明する必要があります。

この考え方は、コンピューター科学で「不可能性の証明」を行うときによく使われます。

以下では、具体的に整列問題の最悪時間計算量の下界証明をしてみます。