アルゴリズム解析のソースを表示

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

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

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

漸近的でない正確な効率がわかる場合もあるが、そのためには「[[計算モデル]]」と呼ばれるアルゴリズムの特定の実装を仮定する必要がある。計算モデルは[[チューリング機械]]のような[[計算模型|抽象化された機械]]を使うか、個々の命令の実行時間が変化しないと仮定することが多い（例えば実際のコンピュータではキャッシュにヒットするかしないかでは大きく実行時間が異なるが、アルゴリズム解析では一般にそれを無視する）。例えば、[[二分探索]]で N 個のソートされた数から探索する場合、1回の参照を一定の単位時間でできるとした場合、回答を得るまでに最大で log<sub>2</sub> N+1 単位時間を要する。<!-- 正確な見積もりはアルゴリズムを実装して使用する人々にとって有用であり、実行に要する時間を正確に知ることができる。一部の人々（例えばゲームプログラマ）にとっては、隠れた定数が成功と失敗を分けることもある。-->

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

一般に次の2つのコストモデルが使われる<ref name="AhoHopcroft1974">{{Cite book |author1=Alfred V. Aho |author1-link=アルフレッド・エイホ |author2=John E. Hopcroft |author2-link=ジョン・ホップクロフト |author3=Jeffrey D. Ullman |title=The design and analysis of computer algorithms |year=1974 |publisher=Addison-Wesley Pub. Co.}}, section 1.3</ref><ref name="Hromkovič2004">{{Cite book |author=Juraj Hromkovič |title=Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography |url= https://books.google.co.jp/books?id=KpNet-n262QC&pg=PA177&redir_esc=y&hl=ja |year=2004 |publisher=Springer |isbn=978-3-540-14015-3 |pages=177–178}}</ref><ref name="Ausiello1999">{{Cite book |author=Giorgio Ausiello |title=Complexity and approximation: combinatorial optimization problems and their approximability properties |url= https://books.google.co.jp/books?id=Yxxw90d9AuMC&pg=PA3&redir_esc=y&hl=ja |year=1999 |publisher=Springer |isbn=978-3-540-65431-5 |pages=3–8}}</ref><ref name=Wegener20>{{Citation |last1=Wegener |first1=Ingo |title=Complexity theory: exploring the limits of efficient algorithms |publisher=[[シュプリンガー・サイエンス・アンド・ビジネス・メディア|Springer-Verlag]] |location=Berlin, New York |isbn=978-3-540-21045-0 |year=2005 |page=20 |url= https://books.google.co.jp/books?id=u7DZSDSUYlQC&pg=PA20&redir_esc=y&hl=ja}}</ref><ref name="Tarjan1983">{{Cite book |author=Robert Endre Tarjan |authorlink=ロバート・タージャン |title=Data structures and network algorithms |url= https://books.google.co.jp/books?id=JiC7mIqg-X4C&pg=PA3&redir_esc=y&hl=ja |year=1983 |publisher=SIAM |isbn=978-0-89871-187-5 |pages=3–7}}</ref>。
; 一様コストモデル
: マシンによる全ての演算について、一定のコストを割り当てる。数値の大きさは考慮しない。
; 対数コストモデル
: マシンによる全ての演算について、計算対象となる数値のビット数に比例したコストを割り当てる。

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

見過ごされがちな重要な観点として、公表されている問題の下限（最良実行時間）は実際のコンピュータよりも制限された計算モデルについてのものであることが多いという点が挙げられる。そのため、実際にアルゴリズムを実装し実行してみると、想定していたよりも実行時間が短くなる（成長が遅い）ことがある<ref>[http://cstheory.stackexchange.com/questions/608/examples-of-the-price-of-abstraction Examples of the price of abstraction?], cstheory.stackexchange.com</ref>。

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

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

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

{| class="wikitable"
|-
! ''n''（リストの大きさ）
! コンピュータAの実行時間<br />（ナノ秒単位）
! コンピュータBの実行時間<br />（ナノ秒単位）
|-
| 15
| 7 
| 100,000 
|-
| 65
| 32 
| 150,000 
|-
| 250
| 125 
| 200,000 
|-
| 1,000
| 500 
| 250,000 
|}

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

{| class="wikitable"
|-
! ''n''（リストの大きさ）
! コンピュータAの実行時間<br />（ナノ秒単位）
! コンピュータBの実行時間<br />（ナノ秒単位）
|-
| 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 &times; 10<sup>12</sup>
| 31,536 &times; 10<sup>12</sup> ナノ秒、<br />または1年
| 1,375,000 ナノ秒,<br />または 1.375 ミリ秒
|}

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

=== 成長のオーダー ===
{{Main|ランダウの記号}}
大まかに言えば、あるアルゴリズムの入力サイズ ''n'' がある特定の値を超えたとき、その成長率がある[[関数 (数学)|数学関数]]のオーダーであるとは、その関数 ''f(n)'' に正の定数をかけた値がそのアルゴリズムの実行時間の{{仮リンク|漸近解析|en|Asymptotic analysis|label=上限}}を与えることを意味する。言い換えれば、入力サイズ ''n'' が ''n<sub>0</sub>'' より大きいとき、そのアルゴリズムの実行時間は ''c &times; f(n)'' を越えない（''c''は定数）。この概念はO記法で表現されることが多い。例えば、[[挿入ソート]]の実行時間は{{仮リンク|二次関数的成長|en|quadratic growth|label=二次関数的に成長}}するので、挿入ソートのオーダーは ''O(n<sup>2</sup>)'' と言える。

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

=== 経験的な成長のオーダー ===
実行時間が ''{{Math|&asymp; k n<sup>a</sup>}}'' という法則に従うと仮定し、2つの入力サイズ <math>\{n1, n2\}</math> における実測値 <math>\{t1, t2\}</math> から係数 ''a'' を求めるとすると<ref>[http://rjlipton.wordpress.com/2009/07/24/how-to-avoid-o-abuse-and-bribes/ How To Avoid O-Abuse and Bribes], at the blog "Gödel’s Lost Letter and P=NP" by R. J. Lipton, professor of Computer Science at Georgia Tech, recounting idea by Robert Sedgewick</ref>、<math>t_2/t_1 = (n_2/n_1)^a</math> という式が成り立つので <math>a = \log(t_2/t_1) / \log(n_2/n_1)</math> となる。成長のオーダーがこの法則に従うなら、実測から得た ''a'' の値は異なる実測値同士から求めた場合も一定となるはずである。オーダーがその法則に従わないなら、''a'' は一定にならない。それでも、このような比較は2つのアルゴリズムの「経験的な局所的成長オーダー」の挙動を比較するのに役立つ。先に挙げた表に適用してみると次のようになる。

{| class="wikitable"
|-
! ''n''（リストの大きさ）
! コンピュータAの実行時間<br />（ナノ秒単位）
! ローカルな成長オーダー<br />(n^_)
! コンピュータBの実行時間<br />（ナノ秒単位）
! ローカルな成長オーダー<br />(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 を得る''
 2    '''if''' 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!"

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

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

:<math>T_1 + T_2 + T_3 + T_7 \,</math>

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

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

:<math>T_6 + 2T_6 + 3T_6 + \cdots + (n-1) T_6 + n T_6</math>

この式は次のように[[因数分解]]できる<ref><math>1 + 2 + 3 + \cdots + (n-1) + n = \frac{n(n+1)}{2}</math> は[[数学的帰納法]]で証明できる。</ref>。

:<math>T_6 \left[ 1 + 2 + 3 + \cdots + (n-1) + n \right] = T_6 \left[ \frac{1}{2} (n^2 + n) \right] </math>

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

:<math>2T_5 + 3T_5 + 4T_5 + \cdots + (n-1) T_5 + n T_5 + (n + 1) T_5</math>
:<br /><math> = T_5 + 2T_5 + 3T_5 + 4T_5 + \cdots + (n-1)T_5 + nT_5 + (n+1)T_5 - T_5</math>

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

:<math>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</math>

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

:<math>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</math>

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

:<math>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
</math>

経験的に最も次数の高い項が成長率を支配することが知られており、それが実行時間のオーダーを定義する。この例では ''n<sup>2</sup>'' が最も次数が高いので、f(n) = O(n<sup>2</sup>) という結論が得られる。形式的には次のように証明される。
<blockquote>
<math>\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 \le cn^2,\ n \ge n_0</math> の証明
<br /><br />
<math>\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</math>

<br /><math>\le ( n^2 + n )T_6 + ( n^2 + 3n )T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7</math> （ここで ''n ≥ 0''）

<br /><br />k が [T<sub>1</sub>..T<sub>7</sub>] 以上の定数とすると
<br /><br /><math>T_6( n^2 + n ) + T_5( n^2 + 3n ) + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le k( n^2 + n ) + k( n^2 + 3n ) + kn + 5k</math>
<br /><math>= 2kn^2 + 5kn + 5k \le 2kn^2 + 5kn^2 + 5kn^2</math> (''for n ≥ 1'') <math>= 12kn^2</math>

<br /><br />したがって <math>\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 \le cn^2, n \ge n_0</math> ここで <math>c = 12k, n_0 = 1</math>
</blockquote>

このアルゴリズムを解析するより洗練された手法としては、[T<sub>1</sub>..T<sub>7</sub>] をそれぞれの実際にかかる時間以上の単位時間と等しいと宣言する方法がある。その場合、このアルゴリズムの実行時間は次のようになる<ref>この方法では、上述の方法とは異なり、ループの条件部で消費される定数時間を無視しているが、そのような省略が最終的な結果に影響しないことは自明である。</ref>。
<blockquote><math>4+\sum_{i=1}^n i\leq 4+\sum_{i=1}^n n=4+n^2\leq5n^2</math> (''for n ≥ 1'') <math>=O(n^2)</math></blockquote>

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

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

この場合、ファイルサイズ ''n'' が増大するとメモリ使用量は[[指数関数的成長]]を示し、そのオーダーは ''O(2<sup>n</sup>)'' となる<ref>なお、この成長オーダーは急速すぎるので、実用には耐えない。</ref>。

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

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

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

== 脚注 ==
{{Reflist}}

== 参考文献 ==
*{{Cite book |first=Thomas H. |last=Cormen  |first2=Charles E. |last2=Leiserson |authorlink3=ロナルド・リベスト |first3=Ronald L. |last3=Rivest |name-list-style=amp |first4=Clifford |last4=Stein |title=Introduction to Algorithms |edition=Second |publisher=MIT Press and McGraw-Hill |location=Cambridge, MA |year=2001 |isbn=0-262-03293-7 |others=Chapter 1: Foundations |pages=3–122 }}
*{{Cite book|title=Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching |edition=3rd |first=Robert |last=Sedgewick |location=Reading, MA |publisher=Addison-Wesley Professional |year=1998 |isbn=978-0-201-31452-6 }}
*{{Cite book|title=[[The Art of Computer Programming]] |authorlink=ドナルド・クヌース |first=Donald |last=Knuth |location= |publisher=Addison-Wesley |isbn= |year= }}
*{{Cite book|first=Daniel A. |last=Greene |first2=Donald E. |last2=Knuth |title=Mathematics for the Analysis of Algorithms |edition=Second |location= |publisher=Birkhäuser |year=1982 |isbn=3-7643-3102-X }}
*{{Cite book |first=Oded |last=Goldreich |title=Computational Complexity: A Conceptual Perspective |location= |publisher=[[ケンブリッジ大学出版局|Cambridge University Press]] |year=2010 |isbn=978-0-521-88473-0 }}

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

{{DEFAULTSORT:あるこりすむかいせき}}
[[Category:アルゴリズム解析|*]]
[[Category:計算複雑性理論]]
[[Category:アルゴリズム]]
[[Category:数学に関する記事]]