algorithm - アルゴリズムの償却分析

Question

私は現在、償却分析を読んでいます。アルゴリズムの平均または最悪のケースの動作を計算するために実行する通常の分析とどのように異なるかを完全に理解することはできません。誰かがソートなどの例で説明できますか?

Answer 1

平均- 確率分析。平均は可能なすべての入力に関連しており、アルゴリズムの実行時間の推定値です。

amortized - アルゴリズムへの呼び出しのバッチに関連して計算された非確率的分析。

例 - 動的サイズのスタック:

あるサイズのスタックを定義し、スペースを使い果たすたびに、古いサイズの 2 倍を割り当て、要素を新しい場所にコピーするとします。

全体的な費用は次のとおりです。

• 挿入 \ 削除ごとに O(1)

• スタックがいっぱいの場合、挿入 (割り当てとコピー) ごとに O(n)

n 個の挿入にかかる時間は?

O(n^2) と言うかもしれませんが、すべての挿入に対して O(n) を支払うわけではありません。したがって、私たちは悲観的です。正解は、n 回の挿入で O(n) 回です。理由を見てみましょう。

配列サイズ = 1 から始めるとしましょう。

コピーを無視すると、n 回の挿入ごとに O(n) を支払うことになります。

現在、スタックにこれらの数の要素がある場合にのみ、完全なコピーを行います。

1,2,4,8,...,n/2,n

これらのサイズごとにコピーと割り当てを行うため、コストを合計すると次のようになります。

const*(1+2+4+8+...+n/4+n/2+n) = const*(n+n/2+n/4+...+8+4+2+1 ) <= const*n(1+1/2+1/4+1/8+...)

ここで (1+1/2+1/4+1/8+...) = 2

したがって、すべてのコピーに対して O(n) + 実際の n 回の挿入に対して O(n) を支払います

O(n) n 操作の最悪のケース -> O(1) 1 回の操作で償却。