償却解析
償却解析は、当初、aggregate analysis(集計分析)とよばれる手法から出現した。これは現在では償却解析に包含されている。この技術は最初、Robert Tarjanの 1985 年の論文 Amortized Computational Complexity で公式に導入され、これまで使用されてきた共通の確率的手法よりもより強力な分析形態の必要性を主張した。償却は最初非常に明確な種類のアルゴリズム、とりわけ二分木や union 操作( SQL の union を意味しており、共用体のことではないと思われる。)に使用された。しかし、いまや至る所にあり、多くのほかのアルゴリズムの分析時にも活動する。