償却解析
この手法は、どの一連の操作が可能かどうかの知識を必要とする。これは、データ構造の場合には最も一般的である。それは、操作間に固執する状態を持つ。基本的な考え方は、最悪な場合の操作は、そのケースが長期間にわたって再び起こらないように状態を変えることができ、そのコストを"償却する"ということである。 一般に、償却解析を行う 3 つの方法がある。これらはすべて同一の結果を与え、使用法の相違は主に状況および個人の好みである。
Aggregate analysis - これは、 一連の n 回の操作の全コストに関する上限 T(n) を決定し、 償却コストを T(n) / n と計算する。
en:Accounting_method - これは、各操作の各コストを決定し、その即時の実行時間および将来の操作の実行時間への影響を結合する。たいてい、多くの短期実行操作(short-running operations)は少しずつ好ましくない状態の"負債"を蓄積し、一方でレアな長期実行操作(long-running operations)はそれを劇的に減少させる。
en:Potential_method - これは、accounting method と似ているが、後で課金を補償するために、早期に操作に課金する。