DAA-分析の方法論

アルゴリズムのリソース消費を測定するために、この章で説明するようにさまざまな戦略が使用されます。

漸近解析

関数の漸近的振る舞い f(n) の成長を指します f(n) なので n 大きくなります。

通常、の小さな値は無視します n、私たちは通常、大きな入力でプログラムがどれだけ遅くなるかを推定することに関心があるためです。

経験則として、漸近的な成長率が遅いほど、アルゴリズムは優れています。それは常に真実ではありませんが。

たとえば、線形アルゴリズム$ f（n）= d * n + k $は、常に2次アルゴリズム$ f（n）= cn ^ 2 + q $よりも漸近的に優れています。

漸化式を解く

漸化式は、小さい入力での値の観点から関数を説明する方程式または不等式です。再発は通常、分割統治パラダイムで使用されます。

私たちに考えさせてください T(n) サイズの問題の実行時間になる n。

問題のサイズが十分に小さい場合は、 n < c どこ c は定数であり、単純な解には一定の時間がかかります。これは次のように記述されます。 θ(1)。問題を分割すると、サイズが$ \ frac {n} {b} $のサブ問題が多数発生する場合。

問題を解決するために必要な時間は a.T(n/b)。除算に必要な時間を考えるとD(n) サブ問題の結果を組み合わせるのに必要な時間は C(n)、漸化式は次のように表すことができます。

$$ T（n）= \ begin {cases} \：\：\：\：\：\：\：\：\：\：\：\：\：\：\：\：\：\：\： \：\：\：\：\ theta（1）＆if \：n \ leqslant c \\ a T（\ frac {n} {b}）+ D（n）+ C（n）＆else \ end {ケース} $$

漸化式は、次の方法を使用して解くことができます-

Substitution Method −この方法では、限界を推測し、数学的帰納法を使用して、仮定が正しいことを証明します。
Recursion Tree Method −この方法では、各ノードがコストを表す繰り返しツリーが形成されます。
Master’s Theorem −これは、漸化式の複雑さを見つけるためのもう1つの重要な手法です。

償却分析

償却分析は通常、一連の同様の操作が実行される特定のアルゴリズムに使用されます。

償却分析は、一連の操作のコストを個別に制限するのではなく、シーケンス全体の実際のコストに制限を提供します。
償却分析は、平均的なケースの分析とは異なります。確率は償却分析には含まれません。償却分析は、最悪の場合の各操作の平均パフォーマンスを保証します。

設計と分析は密接に関連しているため、これは単なる分析ツールではなく、設計についての考え方です。

集計方法

集計メソッドは、問題のグローバルビューを提供します。この方法では、n 操作には最悪の時間がかかります T(n)合計で。次に、各操作の償却コストは次のようになります。T(n)/n。操作が異なれば時間がかかることもありますが、この方法ではコストの変動は無視されます。

会計方法

この方法では、実際のコストに応じて、さまざまな操作にさまざまな料金が割り当てられます。操作の償却原価が実際原価を超える場合、差額はクレジットとしてオブジェクトに割り当てられます。このクレジットは、償却原価が実際の原価よりも少ない後の操作の支払いに役立ちます。

実際の費用との償却費用が i^th 操作は$ c_ {i} $と$ \ hat {c_ {l}} $であり、

$$ \ displaystyle \ sum \ Limits_ {i = 1} ^ n \ hat {c_ {l}} \ geqslant \ displaystyle \ sum \ limits_ {i = 1} ^ n c_ {i} $$

可能な方法

この方法は、プリペイド作業をクレジットと見なすのではなく、プリペイド作業を位置エネルギーとして表します。このエネルギーは、将来の運用に支払うために解放することができます。

演じれば n 初期データ構造から始まる操作 D₀。よく考えさせてください、c_i 実際の費用として D_i のデータ構造として i^th操作。ポテンシャル関数Фは実数Ф（D_i）、関連する可能性 D_i。償却原価$ \ hat {c_ {l}} $は次のように定義できます。

$$ \ hat {c_ {l}} = c_ {i} + \ Phi（D_ {i}）-\ Phi（D_ {i-1}）$$

したがって、総償却原価は次のようになります。

$$ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ hat {c_ {l}} = \ displaystyle \ sum \ limits_ {i = 1} ^ n（c_ {i} + \ Phi（D_ {i} ）-\ Phi（D_ {i-1}））= \ displaystyle \ sum \ extends_ {i = 1} ^ n c_ {i} + \ Phi（D_ {n}）-\ Phi（D_ {0}）$ $

動的テーブル

テーブルに割り当てられたスペースが十分でない場合は、テーブルをより大きなサイズのテーブルにコピーする必要があります。同様に、多数のメンバーがテーブルから消去される場合は、より小さなサイズでテーブルを再割り当てすることをお勧めします。

償却分析を使用すると、挿入と削除の償却コストが一定であり、動的テーブルの未使用スペースが合計スペースの一定の割合を超えることはないことを示すことができます。

このチュートリアルの次の章では、漸近表記について簡単に説明します。