アルゴリズムの分析

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

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

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

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

コストモデル

時間効率の推定は、ステップの定義に依存します。解析結果が実際の実行時間と適切に一致するためには、ステップの実行に必要な時間が一定値以上であることが保証される必要があります。ここで注意すべき点があります。例えば、一部の解析では2つの数値の加算を1ステップとカウントします。この仮定は、特定の状況では正当化されない場合があります。例えば、計算に含まれる数値が任意の大きさになる場合、1回の加算に必要な時間はもはや一定であるとは仮定できません。

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

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

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

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

実行時分析

実行時解析とは、アルゴリズムの入力サイズ（通常は $n$ と表記）の増加に伴う実行時間（または実行時間）の増加を推定・予測する理論的な分類です。実行時効率はコンピュータサイエンスにおいて非常に重要なテーマです。プログラムの実行は、実装されているアルゴリズムに応じて、数秒、数時間、あるいは数年かかることもあります。ソフトウェアプロファイリング技術は、実際にはアルゴリズムの実行時間を測定するために使用できますが、無限に考えられるすべての入力に対するタイミングデータを提供することはできません。後者は、実行時解析の理論的な手法によってのみ実現できます。

経験的指標の欠点

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

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

n (リストサイズ)	コンピュータAの実行時間（ナノ秒単位）	コンピュータBの実行時間（ナノ秒）
16	8	10万
63	32	15万
250	125	20万
1,000	500	25万

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

n (リストサイズ)	コンピュータAの実行時間（ナノ秒単位）	コンピュータBの実行時間（ナノ秒）
16	8	10万
63	32	15万
250	125	20万
1,000	500	25万
...	...	...
1,000,000	50万	50万
4,000,000	2,000,000	55万
16,000,000	8,000,000	60万
...	...	...
63,072 × 10 ¹²	31,536 × 10 ¹²ナノ秒、または1年	1,375,000ナノ秒、または1.375ミリ秒

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

成長の順序

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

Big O 表記法は、特定のアルゴリズムの最悪ケースのシナリオを表現するのに便利な方法ですが、平均ケースを表現するためにも使用できます。たとえば、クイックソートの最悪ケースのシナリオは $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$ $)$ です。言い換えれば、これは、実行時間と入力サイズのlog-log プロット上の経験的直線の傾きを、あるサイズポイントで測定することになります。もし成長の順序が実際にべき乗則に従う場合（つまり、対数対数プロット上の線が実際に直線である場合）、 $a$ の経験値は異なる範囲で一定のままであり、そうでない場合は変化します（そして線は曲線になります）。しかし、それでも、任意の2つのアルゴリズムについて、成長挙動の実験的な局所順序を比較することは可能です。上記の表に適用すると、

n (リストサイズ)	コンピュータAの実行時間（ナノ秒単位）	成長の局所的順序(n^_)	コンピュータBの実行時間（ナノ秒）	成長の局所的順序(n^_)
15	7		10万
65	32	1.04	15万	0.28
250	125	1.01	20万	0.21
1,000	500	1.00	25万	0.16
...	...		...
1,000,000	50万	1.00	50万	0.10
4,000,000	2,000,000	1.00	55万	0.07
16,000,000	8,000,000	1.00	60万	0.06
...	...		...

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

実行時の複雑さの評価

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

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

特定のコンピュータは、このアルゴリズムを実行するための各命令を実行するのに、それぞれ異なる時間がかかります。ステップ1で実行されるアクションは最大でT _{1 の}時間を消費し、ステップ2は最大でT _{2 の}時間を消費する、といった具合です。

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

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 ₆時間、内側のループテスト (ステップ 5) に 2 T ₅時間がかかります。外側のループの次のパスでは、 j は 1 から 2 まで反復されます。内側のループは 2 パスを実行するため、内側のループ本体 (ステップ 6) の実行に 2 T ₆時間、内側のループテスト (ステップ 5) に 3 T ₅時間がかかります。

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

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

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

\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{ }}c=12k,n_{0}=1 の場合$

このアルゴリズムをより簡潔に分析するには、[ T ₁ .. T ₇ ] がすべて1単位の時間であると宣言し、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)となります。$

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

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

参照

注記

^ “Knuth: Recent News” . 2016年8月28日.オリジナルより2016年8月28日時点のアーカイブ。
^コーメン、トーマス・H.編 (2009).アルゴリズム入門（第3版）. ケンブリッジ、マサチューセッツ州: MITプレス. pp. 44– 52. ISBN 978-0-262-03384-8. OCLC 311310321 .
^アルフレッド・V・エイホ、ジョン・E・ホップクロフト、ジェフリー・D・ウルマン (1974).コンピュータアルゴリズムの設計と分析. アディソン・ウェズリー出版. ISBN 9780201000290。、セクション1.3
^ Juraj Hromkovič (2004). 『理論計算機科学：オートマトン、計算可能性、複雑性、アルゴリズム、ランダム化、通信、暗号入門』 Springer. pp. 177– 178. ISBN 978-3-540-14015-3。
^ Giorgio Ausiello (1999).複雑性と近似：組合せ最適化問題とその近似可能性. Springer. pp. 3– 8. ISBN 978-3-540-65431-5。
^ Wegener, Ingo (2005),複雑性理論：効率的なアルゴリズムの限界を探る、ベルリン、ニューヨーク：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のブログ「Gödel's Lost Letter and 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。
グリーン、ダニエル・A.;クヌース、ドナルド・E. (1982).アルゴリズム解析のための数学（第2版）. ビルクハウザー. ISBN 3-7643-3102-X。
コーメン, トーマス・H. ;レイサーソン, チャールズ・E. ;リベスト, ロナルド・L. &スタイン, クリフォード(2001). 『アルゴリズム入門』第1章基礎（第2版）. ケンブリッジ, マサチューセッツ州: MIT Press and McGraw-Hill. pp. 3– 122. ISBN 0-262-03293-7。
セジウィック, ロバート(1998). 『C言語アルゴリズム第1-4部：基礎、データ構造、ソート、検索』（第3版）. マサチューセッツ州レディング: Addison-Wesley Professional. ISBN 978-0-201-31452-6。
ドナルド・クヌース著『コンピュータプログラミングの芸術』アディソン・ウェスレー社。
ゴールドライヒ、オデッド（2010年）『計算複雑性：概念的視点』ケンブリッジ大学出版局、ISBN 978-0-521-88473-0。

外部リンク

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

[1] “Knuth: Recent News” . 2016年8月28日.オリジナルより2016年8月28日時点のアーカイブ。

[2] コーメン、トーマス・H.編 (2009).アルゴリズム入門（第3版）. ケンブリッジ、マサチューセッツ州: MITプレス. pp. 44– 52. ISBN 978-0-262-03384-8. OCLC 311310321 .

[AhoHopcroft1974-3] アルフレッド・V・エイホ、ジョン・E・ホップクロフト、ジェフリー・D・ウルマン (1974).コンピュータアルゴリズムの設計と分析. アディソン・ウェズリー出版. 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).複雑性と近似：組合せ最適化問題とその近似可能性. Springer. pp. 3– 8. ISBN 978-3-540-65431-5。

[Wegener20-6] Wegener, Ingo (2005),複雑性理論：効率的なアルゴリズムの限界を探る、ベルリン、ニューヨーク：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のブログ「Gödel's Lost Letter and 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

T 4 (

これは[

[ 12 ]