【ならしけいさんりょう】
ならし計算量（償却解析） とは？
公開:
💡 たまの大仕事も、操作全体の予算で考える
一連の操作の総コストから、1回当たりのコストを評価する考え方。たまに重い操作があっても、その頻度を含めて全体の上限を見積もる。
📌 このページのポイント
- 単発の最悪時間と、操作列全体でならした時間を区別する
- 容量を倍増する動的配列への末尾追加は、代表的な償却O(1)の例
- 入力がランダムだと仮定する平均計算量とは別の分析
ひよこ たまに遅くなる処理を、速いと言っていいの？
ペンギン先生 何を測るかによるよ。ならし計算量は、一連の操作に必要な仕事の合計を考えるんだ。1回だけなら重い処理でも、それが十分まれなら、操作全体では小さな予算に収まることを示せるよ。
ひよこ 具体例がほしいな。
ペンギン先生 容量1から始め、満杯になると容量を2倍にする配列へ8個追加しよう。既存要素のコピーは1個、2個、4個の計7個。追加の書き込み8回と合わせて15回だよ。ここでは1要素の書き込み・コピーをそれぞれ1単位と数えているんだ。
ひよこ 8個より増えても同じ考え方？
ペンギン先生 そうだよ。n回の追加までに起こるコピー数は1、2、4…と増えるけれど、その合計はnに比例する範囲に収まる。だから末尾追加は償却O(1)と評価できるんだ。ただし拡張する1回だけを取り出すと、その時点の要素数に比例した仕事が必要だよ。
ひよこ 「平均すると速い」とは違うの？
ペンギン先生 ランダムな入力の出やすさを平均する話ではないんだ。ここでは空の配列から末尾追加を続けるという条件で、操作列全体の費用を抑えている。応答時間の厳しい処理では、償却値だけでなく1回の最悪時間も確認したいね。
もっと詳しく知りたい人へ
容量を1個ずつ増やしても償却O(1)ですか？
毎回それまでの全要素をコピーするなら、n回の追加でコピー数は0＋1＋…＋(n−1)となり、総コストはO(n²)です。末尾追加の償却O(1)という結論には、容量を一定の倍率で増やすなどの条件が必要です。
まとめ：ざっくりこれだけ覚えればOK！
「ならし計算量（償却解析）」って出てきたら「重い回も含め、操作列全体の費用を割り振る見積もり」と思えればだいたいOK！