アルゴリズムの分析

コンピュータサイエンスにおいて、アルゴリズムの解析とは、アルゴリズムの計算複雑度、つまりアルゴリズムの実行に必要な時間、記憶容量、その他のリソースの量を求めるプロセスです。通常、これには、アルゴリズムの入力サイズと、アルゴリズムが実行するステップ数（時間複雑度）または使用する記憶領域の数（空間複雑度）の関係を表す関数を決定することが含まれます。この関数の値が小さい、または入力サイズの増加に比べて増加が緩やかな場合、アルゴリズムは効率的であると言えます。同じサイズの異なる入力によってアルゴリズムの動作が異なる場合があるため、最良ケース、最悪ケース、平均ケースの記述はすべて実用的な関心事となる可能性があります。特に指定がない限り、アルゴリズムのパフォーマンスを表す関数は通常、アルゴリズムへの最悪ケースの入力から決定される上限値です。

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

アルゴリズムの理論的解析では、漸近的な意味でその複雑さを推定するのが一般的です。つまり、任意の大きな入力に対する複雑さ関数を推定します。この目的のために、ビッグ O 記法、ビッグ ω 記法、ビッグ θ 記法が使用されます。^{[ 2 ]}例えば、二分探索は、検索対象のソート済みリストのサイズ $n$ の対数に比例するステップ数で実行される、つまり $O (log n)$ で実行されると言われ、口語的には「対数時間」で実行されます。通常、漸近的な推定値が使用されます。これは、同じアルゴリズムの異なる実装では効率が異なる可能性があるためです。ただし、与えられたアルゴリズムの任意の 2 つの「妥当な」実装の効率は、隠れた定数と呼ばれる定数乗法因子によって関連付けられています。

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

コストモデル

時間効率の推定値は、ステップの定義に依存します。分析結果が実際の実行時間と適切に対応するためには、ステップの実行に必要な時間が定数で上限が定められていることが保証されなければなりません。ここで注意が必要です。例えば、2つの数値の加算を1ステップとみなす分析もありますが、この仮定は特定の状況では妥当ではない場合があります。例えば、計算に関わる数値が任意に大きくなる可能性がある場合、1回の加算に必要な時間はもはや一定とはみなせません。

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

均一コストモデル（単位コストモデルとも呼ばれる）（および類似のバリエーション）は、関係する数値の大きさに関係なく、すべての機械操作に一定のコストを割り当てます。
the logarithmic cost model, also called logarithmic-cost measurement (and similar variations), assigns a cost to every machine operation proportional to the number of bits involved

The latter is more cumbersome to use, so it is only employed when necessary, for example in the analysis of arbitrary-precision arithmetic algorithms, like those used in cryptography.

A key point which is often overlooked is that published lower bounds for problems are often given for a model of computation that is more restricted than the set of operations that you could use in practice and therefore there are algorithms that are faster than what would naively be thought possible.^[8]

Run-time analysis

Run-time analysis is a theoretical classification that estimates and anticipates the increase in running time (or run-time or execution time) of an algorithm as its input size (usually denoted as $n$ ) increases. Run-time efficiency is a topic of great interest in computer science: A program can take seconds, hours, or even years to finish executing, depending on which algorithm it implements. While software profiling techniques can be used to measure an algorithm's run-time in practice, they cannot provide timing data for all infinitely many possible inputs; the latter can only be achieved by the theoretical methods of run-time analysis.

Shortcomings of empirical metrics

Since algorithms are platform-independent (i.e. a given algorithm can be implemented in an arbitrary programming language on an arbitrary computer running an arbitrary operating system), there are additional significant drawbacks to using an empirical approach to gauge the comparative performance of a given set of algorithms.

Take as an example a program that looks up a specific entry in a sorted list of size n. Suppose this program were implemented on Computer A, a state-of-the-art machine, using a linear search algorithm, and on Computer B, a much slower machine, using a binary search algorithm. Benchmark testing on the two computers running their respective programs might look something like the following:

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

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

成長の順序

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

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

経験的成長次数

実行時間がべき乗則 $t \approx kn a$ に従うと仮定すると、パラメータ $a は$ 、いくつかの問題サイズ点 $n$ $1$ および $n$ $2$ で実行時間 $t$ $1$ および $t$ $2の経験的測定を行い、方程式$ ^{t 2 /} $t$ $1$ $=$ $($ $n$ $2$ $/$ $n$ $1$ $)$ $a を$ $a$ $に関して$ 解くことによって見つけることができます。つまり、 $a$ $= log($ $t$ $2$ $/$ $t$ $1$ $)/log($ $n$ $2$ $/$ $n$ $1$ $)$ です。言い換えれば、これは、あるサイズ点における実行時間と入力サイズの対数-対数プロット上の経験的直線の傾きを測定 $し$ ます。成長の順序が実際にべき乗則に従う場合（したがって、対数-対数グラフ上の線は実際に直線となる）、 $a$ の経験値はさまざまな範囲で一定のままとなり、そうでない場合は変化する（そして線は曲線となる）が、それでも任意の 2 つのアルゴリズムの経験的な局所的成長順序挙動を比較するのに役立つ。上記の表に適用すると次のようになる。

最初のアルゴリズムは、べき乗則に従って線形的な成長を示すことが明確にわかる。2番目のアルゴリズムの経験値は急速に減少しており、別の成長則に従っていることを示唆している。いずれにせよ、経験的には、最初のアルゴリズムよりも局所的な成長次数がはるかに低く（そしてさらに改善している）。

実行時複雑性の評価

与えられたアルゴリズムの最悪ケースにおける実行時間計算量は、アルゴリズムの構造を調べ、いくつかの簡略化された仮定を置くことで評価できる場合がある。次の擬似コードを考えてみよう。

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

特定のコンピュータは、このアルゴリズムを実行するために必要な各命令を実行するのに、それぞれ決まった時間を要します。例えば、ステップ1で実行される処理には最大T1_の時間、ステップ2では最大T2_の時間、といった具合です。

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

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

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

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

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

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

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

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

{\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}}

これは次のように因数分解できます

{\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}}

したがって、このアルゴリズムの総実行時間は次のとおりです。

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}

これは以下になります

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 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}$
${\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 ₇ ] 以上の定数とする。 ${\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}}$ したがって $\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 単位の時間に相当すると宣言することです。これは、アルゴリズムの実行時間が次のように分解されることを意味します。^{[ 12 ]}

$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 n)$ のオーダーになります。これは、メモリリソースの消費量としては非常に速く、おそらく制御不能な増加率です。

定数係数

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

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

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

注記

↑ 「クヌース：最新ニュース」。2016年8月28日。2016年8月28日のオリジナルからアーカイブ済み。
↑ Cormen, Thomas H. 編 (2009).アルゴリズム入門(第 3版). マサチューセッツ州ケンブリッジ: MIT Press. pp. 44–52 . ISBN 978-0-262-03384-8. OCLC 311310321 .
↑ Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman (1974).コンピュータアルゴリズムの設計と解析. Addison-Wesley Pub. Co. ISBN 9780201000290。セクション1.3
↑ Juraj Hromkovič (2004).理論計算機科学：オートマタ、計算可能性、複雑性、アルゴリズム、ランダム化、通信、および暗号入門. Springer. pp. 177–178 . ISBN 978-3-540-14015-3。
↑ Giorgio Ausiello (1999). Complexity and approximation: combinatorial optimization problems and their approximability properties . Springer. pp. 3–8 . ISBN 978-3-540-65431-5。
↑ Wegener, Ingo (2005), Complexity theory: exploring the limits of efficient algorithms , Berlin, New York: Springer-Verlag , p. 20, ISBN 978-3-540-21045-0
↑ Robert Endre Tarjan (1983).データ構造とネットワークアルゴリズム. SIAM. pp. 3–7 . ISBN 978-0-89871-187-5。
↑抽象化の代償の例？、cstheory.stackexchange.com
↑ O-Abuseと賄賂を避ける方法2017年3月8日にWayback Machineにアーカイブされた、ジョージア工科大学のコンピュータサイエンス教授RJ Liptonによるブログ「ゲーデルの失われた手紙とP=NP」より、Robert Sedgewickのアイデアを解説。
↑ forループを終了するには追加の手順が必要なため、n回ではなくn+1回の実行となります。
↑帰納法によって証明できる $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$
↑このアプローチは、上記のアプローチとは異なり、それぞれのループを終了させるループテストによって消費される定数時間を無視していますが、そのような省略が最終結果に影響を与えないことは容易に証明できます。

参考文献

セッジウィック、ロバート；フラジョレ、フィリップ（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 版). Cambridge, MA: MIT Press および McGraw-Hill. pp. 3–122 . ISBN 0-262-03293-7。
セッジウィック、ロバート（1998）。C言語によるアルゴリズム、第1～4部：基礎、データ構造、ソート、検索（第3 版）。マサチューセッツ州レディング：アディソン・ウェスリー・プロフェッショナル。ISBN 978-0-201-31452-6。
クヌース、ドナルド。『コンピュータプログラミングの技法』アディソン・ウェスリー。
ゴールドライヒ、オデッド（2010）。計算複雑性：概念的視点。ケンブリッジ大学出版局。ISBN 978-0-521-88473-0。

外部リンク

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

[1] 「クヌース：最新ニュース」。2016年8月28日。2016年8月28日のオリジナルからアーカイブ済み。

[2] Cormen, Thomas H. 編 (2009).アルゴリズム入門(第 3版). マサチューセッツ州ケンブリッジ: MIT Press. pp. 44–52 . ISBN 978-0-262-03384-8. OCLC 311310321 .

[AhoHopcroft1974-3] Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman (1974).コンピュータアルゴリズムの設計と解析. Addison-Wesley Pub. Co. ISBN 9780201000290。セクション1.3

[Hromkovič2004-4] Juraj Hromkovič (2004).理論計算機科学：オートマタ、計算可能性、複雑性、アルゴリズム、ランダム化、通信、および暗号入門. Springer. pp. 177–178 . ISBN 978-3-540-14015-3。

[Ausiello1999-5] Giorgio Ausiello (1999). Complexity and approximation: combinatorial optimization problems and their approximability properties . Springer. pp. 3–8 . ISBN 978-3-540-65431-5。

[Wegener20-6] Wegener, Ingo (2005), Complexity theory: exploring the limits of efficient algorithms , Berlin, New York: Springer-Verlag , p. 20, ISBN 978-3-540-21045-0

[Tarjan1983-7] Robert Endre Tarjan (1983).データ構造とネットワークアルゴリズム. SIAM. pp. 3–7 . ISBN 978-0-89871-187-5。

[8] 抽象化の代償の例？、cstheory.stackexchange.com

[9] O-Abuseと賄賂を避ける方法2017年3月8日にWayback Machineにアーカイブされた、ジョージア工科大学のコンピュータサイエンス教授RJ Liptonによるブログ「ゲーデルの失われた手紙とP=NP」より、Robert Sedgewickのアイデアを解説。

[10] rループを終了するには追加の手順が必要なため、n回ではなくn+1回の実行となります。

[11] 帰納法によって証明できる $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$

[12] このアプローチは、上記のアプローチとは異なり、それぞれのループを終了させるループテストによって消費される定数時間を無視していますが、そのような省略が最終結果に影響を与えないことは容易に証明できます。

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[8]

t 2 /

T4 ( n

[ 11 ]

[ 12 ]

アルゴリズムの分析

コストモデル

Run-time analysis

Shortcomings of empirical metrics

成長の順序

経験的成長次数

実行時複雑性の評価

その他の資源の成長率分析

関連性

定数係数

関連項目

注記

参考文献

外部リンク

関連するトピック

バイナリ

線形検索

コンピュータサイエンス

アルゴリズム