アルゴリズム解析

アルゴリズム解析︵アルゴリズムかいせき︶とは、アルゴリズムの実行に必要とされるリソース︵時間や記憶領域︶量を見積もることである。多くのアルゴリズムは任意長の入力を受け付けるよう設計されている。アルゴリズムの﹁効率﹂や﹁複雑さ﹂は一般に、入力長からそのアルゴリズムを実行するのに必要なステップ数︵時間複雑性︶や記憶領域サイズ︵空間複雑性︶への関数として表される。

アルゴリズム解析は計算複雑性理論の重要な一分野である。計算複雑性理論では、与えられた計算問題を解くアルゴリズムが必要とするリソースを理論的に見積もる。この見積もりにより効率的なアルゴリズムを設計する指針が得られることがある。

アルゴリズム解析ではふつう、漸近的︵asymptotic︶な意味で複雑性を見積もる。すなわち、ある程度大きな入力長の際の複雑性関数を見積もる。このためにO記法、Ω記法、Θ記法が用いられる。例えば、二分探索のステップ数は入力サイズの対数に比例し、これを O(log(n)) と表記したり、﹁対数時間﹂と称したりする。このような漸近的な見積もりを用いるのは、同じアルゴリズムでも実装の違いにより差が出るのを捨象するためである。異なる妥当な実装による効率の違いは定数倍に留まる。この定数を隠れた定数︵hidden constant︶と呼ぶ。

漸近的でない正確な効率がわかる場合もあるが、そのためには﹁計算モデル﹂と呼ばれるアルゴリズムの特定の実装を仮定する必要がある。計算モデルはチューリング機械のような抽象化された機械を使うか、個々の命令の実行時間が変化しないと仮定することが多い︵例えば実際のコンピュータではキャッシュにヒットするかしないかでは大きく実行時間が異なるが、アルゴリズム解析では一般にそれを無視する︶。例えば、二分探索でN個のソートされた数から探索する場合、1回の参照を一定の単位時間でできるとした場合、回答を得るまでに最大で log₂ N+1 単位時間を要する。

コストモデル

時間効率の見積もりはステップとして定義するものに依存する。意味のある解析をするには、各ステップの実行時間の上限が一定でなければならない。例えば、2つの数の加算を1ステップと仮定したとしよう。この仮定は場合によっては正しくない。例えば数が極めて大きくなれば、加算が一定時間で完了するとは限らないからである︵紙と鉛筆で2桁の加算をする場合と1000桁の加算をする場合を比べていただきたい︶。

一般に次の2つのコストモデルが使われる。

一様コストモデル

マシンによる全ての演算について、一定のコストを割り当てる。数値の大きさは考慮しない。

対数コストモデル

マシンによる全ての演算について、計算対象となる数値のビット数に比例したコストを割り当てる。

後者の方がより複雑になるので、任意精度演算アルゴリズムなどそれが必要となる場合でしか使用されない。任意精度演算は例えば暗号理論で必要とされる。

見過ごされがちな重要な観点として、公表されている問題の下限︵最良実行時間︶は実際のコンピュータよりも制限された計算モデルについてのものであることが多いという点が挙げられる。そのため、実際にアルゴリズムを実装し実行してみると、想定していたよりも実行時間が短くなる︵成長が遅い︶ことがある。

実行時間解析

実行時間解析とは、アルゴリズムの入力サイズ︵通常 nと記される︶が増大したときの実行時間の増大を評価し推定することで、アルゴリズムを理論的に分類することである。実行時間効率は計算機科学の重要な関心事である。プログラムが完了するまでに数秒で済むのか、数時間かかるのか、1年以上かかるのかは、実装したアルゴリズムに依存する︵アルゴリズムの実行時間を実測して解析するのは性能解析と呼ばれる︶。

実測の問題点

アルゴリズムはプラットフォームに依存しない︵すなわち、アルゴリズムは任意のオペレーティングシステムが動作する任意のコンピュータ上で任意のプログラミング言語で実装できる︶ので、複数のアルゴリズムの性能を比較するのに経験的技法︵実測値︶を用いるのはあまりにも問題が多い。

例として、大きさ nのソートされたリストから特定のエントリを検索するプログラムを考える。そして、最新型の高性能なコンピュータAでは線型探索アルゴリズムでプログラムを実装し、古い低性能なコンピュータBでは二分探索アルゴリズムでプログラムを実装したとする。それら2つのコンピュータでそれぞれのプログラムのベンチマークテストを実施し、次のような結果が得られたとする。

n（リストの大きさ）	コンピュータAの実行時間 （ナノ秒単位）	コンピュータBの実行時間 （ナノ秒単位）
15	7	100,000
65	32	150,000
250	125	200,000
1,000	500	250,000

この測定結果を見ると、コンピュータAで実行したアルゴリズムの方がコンピュータBのそれよりも遥かに高速だと結論しそうになる。しかし、入力リストの大きさを十分大きくすると、その結論は全くの間違いだったことが判明する。

n（リストの大きさ）	コンピュータAの実行時間 （ナノ秒単位）	コンピュータBの実行時間 （ナノ秒単位）
15	7	100,000
65	32	150,000
250	125	200,000
1,000	500	250,000
...	...	...
1,000,000	500,000	500,000
4,000,000	2,000,000	550,000
16,000,000	8,000,000	600,000
...	...	...
63,072 × 1012	31,536 × 1012 ナノ秒、 または1年	1,375,000 ナノ秒, または 1.375 ミリ秒

線型探索プログラムを実行したコンピュータAでの成長率︵実行時間の増加率︶は線型性を示す。すなわち、そのプログラムの実行時間は入力サイズに比例している。入力サイズが2倍になれば実行時間も2倍になり、入力サイズが4倍になれば実行時間も4倍になる、という具合である。一方コンピュータBでは二分探索プログラムを実行したので、成長率は対数的になる。入力サイズが2倍になったとき、実行時間の増加は一定である︵この例では25,000ナノ秒︶。表面上コンピュータAの方が高速でも、コンピュータBの方が成長率が低い︵遅い︶ので、入力サイズが大きくなれば必然的にコンピュータBの方が勝つことになる。

成長のオーダー

詳細は「ランダウの記号」を参照

大まかに言えば、あるアルゴリズムの入力サイズ nがある特定の値を超えたとき、その成長率がある数学関数のオーダーであるとは、その関数 f(n) に正の定数をかけた値がそのアルゴリズムの実行時間の上限を与えることを意味する。言い換えれば、入力サイズ nが n₀ より大きいとき、そのアルゴリズムの実行時間は c × f(n) を越えない︵cは定数︶。この概念はO記法で表現されることが多い。例えば、挿入ソートの実行時間は二次関数的に成長するので、挿入ソートのオーダーは O(n²) と言える。

O記法はアルゴリズムの最悪の場合を表現するのによく使われるが、平均的なケースを表すのに使われることもある。例えばクイックソートの場合、最悪では O(n²) だが、平均では O(n log n) となる。

経験的な成長のオーダー

実行時間が ≈ k n^a という法則に従うと仮定し、2つの入力サイズ $\{n1,n2\}$  における実測値 $\{t1,t2\}$  から係数 aを求めるとすると、$t_{2}/t_{1}=(n_{2}/n_{1})^{a}$  という式が成り立つので $a=\log(t_{2}/t_{1})/\log(n_{2}/n_{1})$  となる。成長のオーダーがこの法則に従うなら、実測から得た aの値は異なる実測値同士から求めた場合も一定となるはずである。オーダーがその法則に従わないなら、a は一定にならない。それでも、このような比較は2つのアルゴリズムの﹁経験的な局所的成長オーダー﹂の挙動を比較するのに役立つ。先に挙げた表に適用してみると次のようになる。

n（リストの大きさ）	コンピュータAの実行時間 （ナノ秒単位）	ローカルな成長オーダー (n^_)	コンピュータBの実行時間 （ナノ秒単位）	ローカルな成長オーダー (n^_)
15	7		100,000
65	32	1.04	150,000	0.28
250	125	1.01	200,000	0.21
1,000	500	1.00	250,000	0.16
...	...		...
1,000,000	500,000	1.00	500,000	0.10
4,000,000	2,000,000	1.00	550,000	0.07
16,000,000	8,000,000	1.00	600,000	0.06
...	...		...

コンピュータAのアルゴリズムはこの法則に従って線型オーダーの成長を示していることが明らかである。コンピュータBでは aが急速に小さくなっており、成長の法則が異なることを示唆している。また、局所的成長オーダーはBの方が小さい︵すなわちアルゴリズムの効率がよい︶ことが経験的に判明する。

実行時間複雑性の評価

与えられたアルゴリズムの最悪ケースの実行時間複雑性は、そのアルゴリズムの構造を調べ、いくつかの単純化仮定をすることで評価できることがある。次の擬似コードを見てみよう。

1入力から正の整数nを得る2if n > 10
3        print "This might take a while..."
4    for i = 1 to n
5        for j = 1 to i
6            print i * j
7    print "Done!"

与えられたコンピュータはこのアルゴリズムの実行で使われる個々の命令の処理に何らかの離散時間かかるだろう。命令の処理にかかる時間は命令の種類やコンピュータの実装によって変化するが、決定論的に得られるものとする。ステップ1の動作にかかる時間をT₁、ステップ2にかかる時間をT₂ などとする。

上のアルゴリズムで、ステップ1、2、7はそれぞれ1回しか実行されない。最悪の場合、ステップ3も1回だけ実行される。したがって、ステップ1、2、3、7の実行にかかる時間は次のようになる。

$T_{1}+T_{2}+T_{3}+T_{7}\,$ 

ループになっているステップ4、5、6の評価には若干の巧妙さが必要となる。外側のループの条件であるステップ4は ( n + 1 ) 回実行され︵ループの終了判定に追加のステップが必要であるため、実行回数はn回ではなく n + 1 回となる︶、T₄( n + 1 ) という時間がかかることになる。一方内側のループのループ回数はiの値で決まり、それは1からnまで順次変化する。最初に外側のループを通ったとき、jの変化する範囲は1から1までである。内側のループを1回だけ通ると、ループ本体︵ステップ6︶にかかる時間はT₆、内側ループの条件︵ステップ5︶にかかる時間は 2T₅となる。外側のループの次の反復では、jは1から2まで変化する。内側のループは2回通るので、内側ループ本体︵ステップ6︶にかかる時間は 2T₆、内側ループの条件︵ステップ5︶にかかる時間は 3T₅ となる。

要するに、内側ループの本体にかかる時間は、次のような等差数列で表される。

$T_{6}+2T_{6}+3T_{6}+\cdots +(n-1)T_{6}+nT_{6}$ 

この式は次のように因数分解できる。

$T_{6}\left[1+2+3+\cdots +(n-1)+n\right]=T_{6}\left[{\frac {1}{2}}(n^{2}+n)\right]$ 

内側のループの条件部にかかる時間の総計も同様に次のように得られる。

$2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}$ 


$=T_{5}+2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}-T_{5}$ 

これを因数分解すると次のようになる。

$T_{5}\left[1+2+3+\cdots +(n-1)+n+(n+1)\right]-T_{5}=T_{5}\left[{\frac {1}{2}}(n^{2}+3n+2)\right]-T_{5}$ 

以上からこのアルゴリズムにかかる時間の総和は次のようになる。

${\displaystyle f($n)=T_{1}+T_{2}+T_{3}+T_{7}+(n+1)T_{4}+\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n+2)\right]T_{5}-T_{5}}  

これを整理すると次のようになる。

${\displaystyle f($n)=\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}}  

経験的に最も次数の高い項が成長率を支配することが知られており、それが実行時間のオーダーを定義する。この例では n²が最も次数が高いので、f(n) = O(n²) という結論が得られる。形式的には次のように証明される。


$\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$  の証明

$\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}$ 

$\leq (n^{2}+n)T_{6}+(n^{2}+3n)T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}$  ︵ここで n ≥ 0︶


kが [T₁..T₇] 以上の定数とすると

$T_{6}(n^{2}+n)+T_{5}(n^{2}+3n)+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq k(n^{2}+n)+k(n^{2}+3n)+kn+5k$ 
$=2kn^{2}+5kn+5k\leq 2kn^{2}+5kn^{2}+5kn^{2}$  (for n ≥ 1) $=12kn^{2}$ 


したがって $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}$  ここで $c=12k,n_{0}=1$ 


このアルゴリズムを解析するより洗練された手法としては、[T₁..T₇] をそれぞれの実際にかかる時間以上の単位時間と等しいと宣言する方法がある。その場合、このアルゴリズムの実行時間は次のようになる。

$4+\sum _{i=1}^{n}i\leq 4+\sum _{i=1}^{n}n=4+n^{2}\leq 5n^{2}$  (for n ≥ 1) $=O(n^{2})$ 

他のリソースの成長率解析

実行時間解析の方法論は記憶領域の使用量などの成長率の推定にも応用できる。例えば、あるファイルの大きさに基づいて使用するメモリの確保量を変更するプログラムの擬似コードは次のようになる。

while (ファイルはオープン中)
    let n = ファイルのサイズ
    for ファイルサイズが100,000キロバイト増加するごとに
        確保するメモリ量を倍にする

この場合、ファイルサイズ nが増大するとメモリ使用量は指数関数的成長を示し、そのオーダーは O(2ⁿ) となる。

意義

非効率なアルゴリズムを使用したためにシステム性能に重大な影響を与えることがあるため、アルゴリズム解析は実用的な意味でも重要である。

︵その時点での計算機のスペックとの相対として︶膨大なデータを扱う場合、そのオーダーによっては、非効率なアルゴリズムは役に立たない。非効率なアルゴリズムは、たとえば時間や記憶領域を無駄に浪費する。

一方で、ただ単に﹁実行時間が重要な用途だから﹂というだけでアルゴリズムに凝るのは、大抵は単なる無駄である。例えば探索について、配列に全て放り込んで、端から探すだけという単純な実装が、データ数が少ない場合にはそれが最も実行時間が少ない、という場合も多い。実例としてはUnixのディレクトリエントリの扱いは古くはそのような実装であった。ボトルネックになる、あるいは膨大なデータになると、あらかじめ確実にわかっているのでなければ、改良する余裕のある、しかし単純な設計でまずは実装し、計測・測定の後に効率化にとりかからなければならない。

参考文献

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford (2001). Introduction to Algorithms. Chapter 1: Foundations (Second ed.). Cambridge, MA: MIT Press and McGraw-Hill. pp. 3–122. ISBN 0-262-03293-7 
• Sedgewick, Robert (1998). Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching (3rd ed.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-31452-6 
• Knuth, Donald. The Art of Computer Programming. Addison-Wesley 
• Greene, Daniel A.; Knuth, Donald E. (1982). Mathematics for the Analysis of Algorithms (Second ed.). Birkhäuser. ISBN 3-7643-3102-X 
• Goldreich, Oded (2010). Computational Complexity: A Conceptual Perspective. Cambridge University Press. ISBN 978-0-521-88473-0 

関連項目

• ランダウの記号
• 計算複雑性理論
• NP完全問題
• 数値解析
• 最適化 (情報工学)
• 性能解析
• ドナルド・クヌース
• 最悪実行時間