償却計算量とは何か - 今日も窓辺でプログラム

時間計算量というと、平均計算量と最悪計算量についてはよく見聞きしましたが、償却計算量という言葉を知らなかったので、それについてまとめておきます。

時間計算量とは？

まず、そもそも時間計算量とは何でしょうか。Wikipediaによると次のように説明されています。

時間計算量は、あるアルゴリズムを使ったときに問題のインスタンスを解くのに要するステップ数を意味し、入力データの長さ（ビット数などで表現できる）の関数として表される。
計算複雑性理論 - Wikipedia

ランダウの記号を使って $O(n^2)$ や $O(n \log n)$ という形で表記することが多いです。

例：動的配列への要素の挿入

ここからは、配列に含まれている要素数によって、配列のサイズが動的に変化する動的配列を例として扱います。JavaのArrayListなんかが、このように実装されているようです。
*1

動的配列は、最初にサイズが4の領域が確保されるとします。要素を挿入していき、5個目の要素を挿入するときに、それまでの2倍のサイズになるように新しい領域を確保します。9個目の要素を追加するときに、配列はさらにその2倍のサイズになります。

最悪計算量

最悪計算量は、言葉の通りもっとも計算量が大きくなる場合の計算量を意味します。
1つ目の要素を挿入する場合、配列への任意の要素のアクセスは $O(1)$ の時間でできるので、計算量は $O(1)$ です。
問題は、例えば5つ目の要素を挿入する際など、配列の長さが動的に変化する場合です。この場合はメモリ上に新たな領域を確保するのに $O(n)$ の時間が必要になるので、計算量は $O(n)$ となります。

つまり、動的配列に要素を追加する場合の最悪計算量は $O(n)$ となります。

償却計算量

一方償却計算量とは、このようなもののようです。

償却計算量というのは、同じ処理をN回行った時に、1回あたりどれくらいの計算量になるかというものです。
計算量のはなし - 赤い黒歴史を蓄積する

日本語記事はまだありませんが、英語の記事はありました。
Amortized analysis - Wikipedia

例を使って考えましょう。動的配列への要素の挿入を $n$ 回行います。この場合の計算量は、 $n$ 回に1回は先ほど説明したような"最悪"のケースが現れるので、 $O(n)$ になります。
償却計算量は、処理1回あたりの計算量なので、この計算量を $n$ で割った以下の結果が償却計算量となります。
${\displaystyle O(\frac{n}{n}) = O(1) }$