今日も窓辺でプログラムスマートフォン用の表示で見る今日も窓辺でプログラム外資系企業勤めのエンジニアが勉強した内容をまとめておくブログ2016-06-28償却計算量とは何かアルゴリズム時間計算量というと、平均計算量と最悪計算量についてはよく見聞きしましたが、償却計算量という言葉を知らなかったので、それについてまとめておきます。時間計算量とは?まず、そもそも時間計算量とは何でしょうか。Wikipediaによると次のように説明されています。時間計算量は、あるアルゴリズムを使ったときに問題のインスタンスを解くのに要するステップ数を意味し、入力データの長さ(ビット数などで表現できる)の関数として表される。いう形で表記することが多いです。例:動的配列への要素の挿入ここからは、配列に含まれている要素数によって、配列のサイズが動的に変化する動的配列を例として扱います。JavaのArrayListなんかが、このように実装されているようです。*1動的配列は、最初にサイズが4の領域が確保されるとします。要素を挿入していき、5個目の要素を挿入するときに、それまでの2倍のサイズになるように新しい領域を確保します。言葉の通りもっとも計算量が大きくなる場合の計算量を意味します。問題は、例えば5つ目の要素を挿入する際など、配列の長さが動的に変化する場合です。このようなもののようです。償却計算量というのは、同じ処理をN回行った時に、1回あたりどれくらいの計算量になるかというものです。赤い黒歴史を蓄積する日本語記事はまだありませんが、英語の記事はありました。Wikipedia例を使って考えましょう。