Python-償却分析

償却分析では、入力値のデータ分布のスパンを考慮せずに、プログラムの一連の操作の実行時間を推定します。簡単な例は、ソートされたリストで値を見つける方が、ソートされていないリストよりも速いことです。リストがすでにソートされている場合は、データがどの程度分散しているかは関係ありません。ただし、もちろん、リストの長さは、アルゴリズムが最終結果を取得するために実行する必要のあるステップ数を決定するため、影響を及ぼします。

したがって、ソートされたリストを取得する単一のステップの初期コストが高い場合、要素を見つける後続のステップのコストはかなり低くなることがわかります。したがって、償却分析は、一連の操作の最悪の場合の実行時間の限界を見つけるのに役立ちます。償却分析には3つのアプローチがあります。

• Accounting Method−これには、実行される各操作にコストを割り当てることが含まれます。実際の操作が割り当てられた時間よりも早く終了した場合、分析には正のクレジットが蓄積されます。逆のシナリオでは、それは負のクレジットになります。これらの累積クレジットを追跡するために、スタックまたはツリーデータ構造を使用します。早期に実行される操作（リストのソートなど）は償却コストが高くなりますが、順番が遅い操作は、累積クレジットが使用されるため、償却コストが低くなります。したがって、償却原価は実際原価の上限です。

• Potential Method−この方法では、保存されたクレジットは、データ構造の状態の数学関数として将来の操作に使用されます。数学関数と償却原価の評価は等しくなければなりません。したがって、実際のコストが償却コストよりも大きい場合、潜在的なコストが減少し、高価な将来の運用に使用されます。

• Aggregate analysis −この方法では、nステップの総コストの上限を見積もります。償却原価は、総原価とステップ数（n）の単純な除算です。