アルゴリズムの分析

コンピュータサイエンスにおいて、アルゴリズムの分析とは、アルゴリズムの計算の複雑さ、つまりアルゴリズムを実行するために必要な時間、ストレージ、またはその他のリソースの量を見つけるプロセスです。通常、これには、アルゴリズムの入力のサイズと、アルゴリズムが実行するステップの数 (時間の複雑さ) またはアルゴリズムが使用するストレージの場所の数 (空間の複雑さ) を関連付ける関数を決定することが含まれます。この関数の値が小さい場合、または入力のサイズの増加に比べてゆっくりと増加する場合、アルゴリズムは効率的であると言われます。同じサイズの異なる入力によってアルゴリズムの動作が異なる場合があるため、最良、最悪、平均の場合の説明はすべて実用上重要です。特に指定がない限り、アルゴリズムのパフォーマンスを説明する関数は通常、アルゴリズムへの最悪の入力から決定される 上限です。

「アルゴリズムの分析」という用語は、ドナルド・クヌースによって造られました。^{[1]アルゴリズムの分析は、より広範な}計算複雑性理論の重要な部分であり、与えられた計算問題を解決するアルゴリズムに必要なリソースの理論的な推定を提供します。これらの推定は、効率的なアルゴリズムを探索するための合理的な方向性についての洞察を提供します。

アルゴリズムの理論的分析では、漸近的な意味でアルゴリズムの複雑さを推定することが一般的です。つまり、任意の大きさの入力に対する複雑さの関数を推定します。このために、ビッグ O 表記、ビッグオメガ表記、ビッグシータ表記が使用されます。^[2]たとえば、バイナリ検索は、検索するソート済みリストのサイズnの対数に比例するステップ数で実行されると言われており、またはO (log n )で、口語的には「対数時間で」実行されます。通常、漸近的な推定値を使用するのは、同じアルゴリズムの異なる実装では効率が異なる可能性があるためです。ただし、特定のアルゴリズムの任意の 2 つの「合理的な」実装の効率は、隠れた定数と呼ばれる一定の乗法係数によって関連しています。

正確な（漸近的ではない）効率の尺度を計算できる場合もありますが、通常は計算モデルと呼ばれるアルゴリズムの特定の実装に関する特定の仮定が必要になります。計算モデルは、チューリングマシンなどの抽象的なコンピュータで定義したり、特定の操作が単位時間で実行されると仮定したりして定義できます。たとえば、バイナリ検索を適用するソート済みリストにn個の要素があり、リスト内の各要素の検索が単位時間で実行できることを保証できる場合、答えを返すために必要な時間は最大でlog ₂ ( n ) + 1単位です。

時間効率の見積もりは、ステップの定義によって異なります。分析が実際の実行時間に有効に対応するためには、ステップの実行に必要な時間が一定値を超えないようにする必要があります。ここで注意が必要です。たとえば、一部の分析では、2 つの数値の加算を 1 ステップとしてカウントします。この仮定は、特定の状況では正当化されない場合があります。たとえば、計算に含まれる数値が任意の大きさである場合、1 回の加算に必要な時間は一定であるとは想定できなくなります。

一般的に2つのコストモデルが使用される: ^{[3] [4] [5] [6] [7]}

• 均一コストモデルは、単位コストモデル（および同様のバリエーション）とも呼ばれ、関係する数字の大きさに関係なく、すべての機械操作に一定のコストを割り当てます。
• 対数コストモデルは、対数コスト測定（および同様のバリエーション）とも呼ばれ、関与するビット数に比例したコストをすべてのマシン操作に割り当てる。

後者は使用が面倒なので、暗号化で使用されるような任意精度の算術アルゴリズムの分析など、必要な場合にのみ使用されます。

見落とされがちな重要な点は、問題に対して公表されている下限値は、実際に使用できる演算セットよりも制限された計算モデルに対して与えられていることが多く、そのため、単純に考えられていたよりも高速なアルゴリズムが存在するということです。^[8]

実行時分析は、アルゴリズムの入力サイズ(通常はnと表記) が増加するにつれて、アルゴリズムの実行時間(または実行時間または実行時間)がどの程度増加するかを推定および予測する理論的な分類です。実行時の効率は、コンピュータ サイエンスで非常に興味深いトピックです。プログラムの実行には、実装するアルゴリズムに応じて、数秒、数時間、または数年かかることがあります。ソフトウェア プロファイリング技術は、実際にはアルゴリズムの実行時間を測定するために使用できますが、無限に考えられるすべての入力のタイミング データを提供することはできません。後者は、実行時分析の理論的な方法によってのみ実現できます。

アルゴリズムはプラットフォームに依存しないため（つまり、特定のアルゴリズムは、任意のオペレーティングシステムを実行している任意のコンピュータ上の任意のプログラミング言語で実装できます）、特定のアルゴリズムセットの比較パフォーマンスを測定するために経験的アプローチを使用することには、さらに重大な欠点があります。

サイズnのソートされた リスト内の特定のエントリを検索するプログラムを例に挙げます。このプログラムが、最先端のマシンであるコンピュータ A では線形探索アルゴリズムを使用して実装され、はるかに低速なマシンであるコンピュータ B ではバイナリ探索アルゴリズムを使用して実装されているとします。 それぞれのプログラムを実行する 2 台のコンピュータでのベンチマーク テストは、次のようになります。

これらの指標に基づくと、コンピュータ Aがコンピュータ Bよりもはるかに効率の優れたアルゴリズムを実行しているという結論に簡単に飛びつくでしょう。しかし、入力リストのサイズが十分な数に増加すると、その結論が誤りであることが劇的に証明されます。

線形探索プログラムを実行しているコンピュータ A は、線形成長率を示します。プログラムの実行時間は、入力サイズに正比例します。入力サイズを 2 倍にすると実行時間も 2 倍になり、入力サイズを 4 倍にすると実行時間も 4 倍になります。一方、バイナリ探索プログラムを実行しているコンピュータ B は、対数成長率を示します。入力サイズを 4 倍にすると、実行時間は一定量 (この例では 50,000 ナノ秒) だけ増加します。コンピュータ A は表面上はより高速なマシンですが、実行時間ではコンピュータ B がコンピュータ A を必然的に上回ります。これは、コンピュータ B が実行しているアルゴリズムの成長率がはるかに遅いためです。

非公式には、ある入力サイズn を超えると、関数f ( n )に正の定数を掛けたものが、そのアルゴリズムの実行時間の上限または制限を与える場合、そのアルゴリズムは数学関数のオーダーの成長率を示すと言えます。言い換えると、あるn ₀より大きい入力サイズnと定数cに対して、そのアルゴリズムの実行時間はc × f ( n )より大きくなることはありません。この概念は、Big O 表記法を使用してよく表現されます。たとえば、挿入ソートの実行時間は入力サイズが増加するにつれて2 乗で増加するため、挿入ソートはO ( n ² )のオーダーであると言えます。

Big O 表記法は、特定のアルゴリズムの最悪ケースのシナリオを表現するのに便利な方法ですが、平均ケースを表現するためにも使用できます。たとえば、クイックソートの最悪ケースのシナリオはO ( n ² )ですが、平均ケースの実行時間はO ( n log n )です。

実行時間がべき乗則t ≈ kn ^aに従うと仮定すると、係数aは、問題サイズのポイント{ n ₁ , n ₂ } で実行時間{ t ₁ , t ₂ ^{} を経験}的に測定し、t ₂ / t ₁ = ( n ₂ / n ₁ ) ^aを計算してa = log( t ₂ / t ₁ )/log( n ₂ / n ₁ )とすることで見つけることができます [9] 。言い換えると、これは、あるサイズポイントでの実行時間対入力サイズのlog-log プロット上の経験的な直線の傾きを測定します。成長の順序が実際にべき乗則に従う場合 (つまり、log-log プロット上の線が実際に直線である場合)、異なる範囲で一定のままであり、そうでない場合は変化します（線は曲線です）が、それでも、成長挙動の実験的な局所的順序に関して、任意の 2 つのアルゴリズムを比較するのに役立ちます。上記の表に適用すると、

最初のアルゴリズムは、確かにべき乗則に従った線形成長順序を示していることがはっきりとわかります。2 番目のアルゴリズムの実験値は急速に減少しており、別の成長規則に従っていることが示唆されており、いずれにしても、実験的には最初のアルゴリズムよりもローカル成長順序がはるかに低く (さらに改善されています) なっています。

特定のアルゴリズムの最悪のシナリオでの実行時の複雑さは、アルゴリズムの構造を調べ、いくつかの単純化された仮定を行うことで評価できる場合があります。次の疑似コードを考えてみましょう。

1    入力
2    から正の整数nを取得する（ n > 10の場合）
3        印刷「これにはしばらく時間がかかるかもしれません...」
4     （ i = 1からnまで）
5         （j = 1 ～ iの場合）
6             i * jを印刷する
7     「完了！」
と印刷します。

特定のコンピュータでは、このアルゴリズムの実行に関連する各命令を実行するのに、個別の時間がかかります。ステップ 1 で実行されるアクションは最大でT _{1 の時間を消費し、ステップ 2 は最大で}T _{2 の}時間を費やす、などとします。

上記のアルゴリズムでは、ステップ 1、2、および 7 は 1 回だけ実行されます。最悪のケースを評価するには、ステップ 3 も実行されると想定する必要があります。したがって、ステップ 1 ～ 3 とステップ 7 を実行するのにかかる合計時間は次のとおりです。

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

ステップ 4、5、6 のループは評価がより複雑です。ステップ 4 の外側のループ テストは ( n + 1 ) 回実行され、[ 10 ] ^T 4 ₍ n + 1 ) の時間がかかります。一方、内側のループは j の値によって制御され、1 からiまで反復されます。外側のループの最初のパスでは、 j は 1 から 1 まで反復されます。内側のループは 1 パスを実行するため、内側のループ本体 (ステップ 6) の実行にはT _{6 の}時間がかかり、内側のループ テスト (ステップ 5) には 2 T _{5 の}時間がかかります。外側のループの次のパスでは、 j は 1 から 2 まで反復されます。内側のループは 2 パスを実行するため、内側のループ本体 (ステップ 6) の実行には 2 T _{6 の}時間がかかり、内側のループ テスト (ステップ 5) には 3 T _{5 の}時間がかかります。

全体として、内側のループ本体を実行するために必要な合計時間は、等差数列として表すことができます。

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

これは次のように 因数分解できる^[11]

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

内部ループテストの実行に必要な合計時間も同様に評価できます。

${\displaystyle {\begin{aligned}&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}\end{aligned}}}$

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

${\displaystyle {\begin{aligned}&T_{5}\left[1+2+3+\cdots +(n-1)+n+(n+1)\right]-T_{5}\\=&\left[{\frac {1}{2}}(n^{2}+n)\right]T_{5}+(n+1)T_{5}-T_{5}\\=&\left[{\frac {1}{2}}(n^{2}+n)\right]T_{5}+nT_{5}\\=&\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}\end{aligned}}}$

したがって、このアルゴリズムの合計実行時間は次のようになります。

${\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)\right]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 ^{2 が}最高次の項であるため、f ( n ) = O ( n ² )と結論付けることができます。正式には、これは次のように証明できます。

証明してください${\displaystyle \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}}$

${\displaystyle {\begin{aligned}&\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}\ ({\text{for }}n\geq 0)\end{aligned}}}$

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

${\displaystyle {\begin{aligned}&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}\ ({\text{for }}n\geq 1)=12kn^{2}\end{aligned}}}$

${\displaystyle \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}{\text{ for }}c=12k,n_{0}=1}$

このアルゴリズムを分析するよりエレガントなアプローチは、[ T ₁ .. T ₇ ]がすべて1単位の時間に相当すると宣言することであり、1単位がこれらのステップの実際の時間以上になるように選択された単位系で表す。これは、アルゴリズムの実行時間が次のように分類されることを意味します。^[12]

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

実行時分析の方法論は、メモリ領域の消費量など、他の増加率を予測するためにも利用できます。例として、プログラムが管理する ファイルのサイズに基づいてプログラムによるメモリ使用量を管理および再割り当てする次の疑似コードを考えてみます。

ファイルがまだ開いている間 :
     n =ファイルサイズとし、ファイルサイズが100,000キロバイト増加するごとに、予約されたメモリの量が2倍になります。
     
        

この例では、ファイル サイズ n が増加すると、メモリはO (2 ⁿ )のオーダーの指数関数的な増加率で消費されます。これは、メモリリソースの消費量としては非常に急速で、おそらく管理できない増加率です。

アルゴリズム分析は実際には重要です。なぜなら、非効率的なアルゴリズムを誤ってまたは意図せずに使用すると、システム パフォーマンスに重大な影響を与える可能性があるからです。時間に敏感なアプリケーションでは、アルゴリズムの実行に時間がかかりすぎると、その結果が古くなったり役に立たなくなったりする可能性があります。非効率的なアルゴリズムは、実行するために不経済な量の計算能力やストレージを必要とすることになり、これもまた実質的に役に立たなくなります。

アルゴリズムの分析は、通常、特に初等レベルでの漸近的なパフォーマンスに焦点を当てていますが、実際のアプリケーションでは定数係数が重要であり、現実世界のデータは実際には常にサイズが制限されています。制限は通常、アドレス指定可能なメモリのサイズであるため、32 ビット マシンでは 2 ³² = 4 GiB (セグメント化されたメモリを使用する場合はそれ以上)、64 ビット マシンでは 2 ⁶⁴ = 16 EiB です。したがって、サイズが制限されている場合、成長の順序 (時間またはスペース) は定数係数に置き換えることができ、この意味で、すべての実用的なアルゴリズムは、十分に大きな定数または十分に小さなデータに対して O (1)になります。

この解釈は、主に、非常にゆっくりと増加する関数に対して有用です。(2 進)反復対数(log ^{* ) は、すべての実際データ (2 65536}ビット)に対して 5 未満です。(2 進) log-log (log log n ) は、ほぼすべての実際データ (2 ⁶⁴ビット) に対して 6 未満です。また、2 進 log (log n ) は、ほぼすべての実際データ (2 ⁶⁴ビット)に対して 64 未満です。定数時間アルゴリズムのオーバーヘッドによって定数係数が大きくなる場合、たとえば、およびである限り、定数複雑度のアルゴリズムよりも、非定数複雑度のアルゴリズムのほうが実際データに対して効率的である可能性があります。 ${\displaystyle K>k\log \log n}$${\displaystyle K/k>6}$${\displaystyle n<2^{2^{6}}=2^{64}}$

大規模なデータの場合、線形または二次の因子は無視できませんが、小規模なデータの場合は、漸近的に非効率的なアルゴリズムの方が効率的な場合があります。これは特に、漸近的に効率的なアルゴリズム (ここでは、時間計算量が のマージソート) を使用するが、小規模なデータでは、より単純なアルゴリズムの方が高速であるため、漸近的に非効率的なアルゴリズム (ここでは、時間計算量が の挿入ソート) に切り替える Timsort などのハイブリッド アルゴリズムで使用されます。 ${\displaystyle n\log n}$${\displaystyle n^{2}}$

• 償却分析
• 並列アルゴリズムの分析
• 漸近的計算複雑性
• 最良、最悪、平均のケース
• ビッグオー表記
• 計算複雑性理論
• マスター定理（アルゴリズムの分析）
• NP完全
• 数値解析
• 多項式時間
• プログラムの最適化
• プロファイリング（コンピュータプログラミング）
• スケーラビリティ
• 平滑化分析
• 終了分析— プログラムがそもそも終了するかどうかをチェックするサブ問題
• 時間計算量- 一般的なアルゴリズムの増加順序の表が含まれています
• 情報に基づく複雑性

• セジウィック、ロバート、フラジョレ、フィリップ(2013)。アルゴリズム分析入門(第 2 版)。アディソン・ウェズリー。ISBN 978-0-321-90575-8。
• Greene, Daniel A.; Knuth, Donald E. (1982).アルゴリズム解析のための数学(第 2 版). Birkhäuser. ISBN 3-7643-3102-X。
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. & Stein, Clifford (2001)。アルゴリズム入門。第 1 章: 基礎 (第 2 版)。マサチューセッツ州ケンブリッジ: MIT プレスおよび McGraw-Hill。pp. 3–122。ISBN 0-262-03293-7。
• セジウィック、ロバート(1998)。Cアルゴリズム、パート 1-4: 基礎、データ構造、ソート、検索(第 3 版)。マサチューセッツ州レディング: Addison-Wesley Professional。ISBN 978-0-201-31452-6。
• クヌース、ドナルド。『コンピュータプログラミングの芸術』。アディソン・ウェズリー。
• Goldreich, Oded (2010)。計算の複雑さ:概念的視点。ケンブリッジ大学出版局。ISBN 978-0-521-88473-0。

• ウィキメディア・コモンズのアルゴリズムの分析に関連するメディア