DAA-分析の方法論

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

漸近解析

関数 f（n） の漸近的な動作は、 n が大きくなるにつれて f（n） が大きくなることを指します。

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

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

たとえば、線形アルゴリズム$ f（n）= d * n + k $は、常に2次アルゴリズム$ f（n）= c.n ^ 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）＆それ以外\ end \ {cases}

再発関係は、次の方法を使用して解決することができます-

置換方法-この方法では、境界を推測し、数学的帰納法を使用して、仮定が正しいことを証明します。
再帰ツリー方法-この方法では、各ノードがコストを表す再帰ツリーが形成されます。
マスターの定理-これは、再帰関係の複雑さを見つけるためのもう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}

ポテンシャル法

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

初期データ構造 D〜0〜 で始まる n 操作を実行する場合。 c〜i〜 を実際のコストとして、 _ D〜i〜' を i ^ th ^ 操作のデータ構造として考えてみましょう。潜在的な関数Theは、実数Ф（ ' 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 \ limits _ \ {i = 1} ^ n c _ \ {i} + \ Phi（D _ \ {n}） -\ Phi（D _ \ {0}）

ダイナミックテーブル

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

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

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

Design-and-analysis-of-algorithms-methodology

目次