償却解析とは（全体像）
償却解析は、たくさんの操作をまとめて、1回あたりの平均の速さを評価するやり方。1回だけ見ると重い操作でも、長い目でならすと安く済むことを示せる。
身近な例が家計の年間平均。たまに大きな出費（家電の買い替えなど）があっても、月ごとにならせば家計は安定して見える。償却解析も同じで、たまの重い操作を全体でならして評価する。
ここで大事なのは、これは「運がよければ速い」という話ではないこと。どんな順番で操作しても、ならした平均はこのくらいに収まる、という保証を与える評価方法だ。
詳しく：動的配列の例と3つの手法だけ覚えれば戦える
ここが記事の心臓部。償却解析のいちばんの代表例が動的配列の拡張だ。
動的配列の拡張（償却O(1)の例）
| 場面 | 1回のコスト | ならすと |
|---|---|---|
| 空きがあるとき追加 | 速い（O(1)） | — |
| いっぱいで2倍に拡張 | 重い（O(n)・全部コピー） | — |
| 追加の平均（全体） | — | 速い（償却O(1)） |
いっぱいになるたびに容量を2倍にすると、拡張のときだけ重い。でも拡張はだんだん間隔があくので、たくさん追加した全体でならすと、1回あたりはO(1)に収まる。これが「償却O(1)」だ。
評価のやり方には、名前のついた3つの手法がある（名前を知っていれば十分）。
償却解析の3つの手法
| 手法 | 考え方 |
|---|---|
| 集計法 | 全部の総コストを操作の回数で割る |
| 会計法 | 各操作に「仮の貯金」を割り当ててならす |
| ポテンシャル法 | データ構造の状態を関数で表してならす |
つまり、償却解析は「たまの重い操作を全体でならして、1回あたりの平均を見る」評価。動的配列のほか、要素をまとめて取り出す処理などでも使われる、というわけだね。
わかりやすく言い換えると
要するに、償却解析は「ならして平均で見る」やり方だ。
①1回だけ見ると … たまに重い操作がある（容量2倍の拡張など）
②全体でならすと … 重い操作はまれなので、1回あたりは安い
③手法の名前 … 集計法・会計法・ポテンシャル法の3つ
家計の年間平均と同じで、たまの大きな出費を月割りでならすイメージ。これが償却の考え方だ。
試験のツボ
🔴 一番出る：ならして平均で見る
①たまに重い操作があっても全体でならす
②1回あたりの平均の速さを保証する
🔴 次に出る：動的配列の2倍拡張
①拡張のときだけ重い（O(n)）
②全体でならすと1回あたりO(1)（償却O(1)）
🟡 押さえると安定：3つの手法と平均ケースとの違い
①集計法・会計法・ポテンシャル法
②運まかせの平均ではなく、どの順でもならせる保証
よくある間違い
①「償却解析は運がよければ速い、という平均ケースの話」→ ✗ 入力の運に頼らず、どの順で操作してもならした平均は収まる。
②「動的配列への追加はいつも重いO(n)」→ ✗ 拡張のときだけ重い。全体でならすと償却O(1)。
③「償却O(1)は1回の操作が必ずO(1)という意味」→ ✗ 1回では重いこともある。あくまで全体をならした平均がO(1)。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（償却解析の考え方）
償却解析の考え方に関する次の記述のうち、正しいものはどれか。
- 一連の操作を全体でならし、1回あたりの平均の速さを評価する考え方のことだ
- 1回だけの最悪の操作の速さだけを取り出して、それを計算量とする考え方とされる
- 入力の運がよかったときだけの速さを取り出して評価する、平均ケースのことである
- 操作の速さはいっさい評価せず、使うメモリの量だけを見積もる考え方のことだ
解答は 1 だよ。
償却解析は一連の操作を全体でならして、1回あたりの平均の速さを評価する考え方なんだ。家計を年間でならすイメージだよ。
選択肢2の「1回の最悪だけ」、選択肢3の「運がよいときだけ」、選択肢4の「メモリだけ」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 全体でならした平均を見る |
| 2 | ✗ | それは最悪計算量 |
| 3 | ✗ | 運に頼らない評価 |
| 4 | ✗ | 速さを評価する |
オリジナル問題2（動的配列の例）
動的配列の拡張に関する次の記述のうち、正しいものはどれか。
- 動的配列への追加はどんなときも重く、ならしてもO(n)のままで速くならないものだ
- 動的配列は拡張という操作をいっさい行わず、容量は最初から変わらないものとされる
- 拡張のときだけ重いが、全体でならすと1回あたりO(1)（償却O(1)）に収まる
- 動的配列の追加はつねに一瞬で、容量を2倍にする処理も軽い操作のことである
解答は 3 だよ。
動的配列は拡張のときだけ重い（O(n)）けど、全体でならすと追加は1回あたりO(1)（償却O(1)）に収まるんだ。拡張の間隔がだんだんあくからだよ。
選択肢1の「ならしてもO(n)」、選択肢2の「拡張しない」、選択肢4の「拡張も軽い」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | ならすと償却O(1) |
| 2 | ✗ | いっぱいで拡張する |
| 3 | ✓ | 全体でならすと償却O(1) |
| 4 | ✗ | 拡張のときは重い |
オリジナル問題3（平均ケースとの違い）
償却解析と平均ケースの違いに関する次の記述のうち、正しいものはどれか。
- 償却解析は入力の運に頼り、平均ケースは運に頼らないという、逆の関係になる
- 償却解析は入力の運に頼らず、どの順で操作してもならした平均が収まることを示す
- 償却解析と平均ケースはまったく同じ言葉で、両者に違いは存在していないものだ
- 償却解析は1回の操作のメモリ量、平均ケースは速さを見るという違いがあるとされる
解答は 2 だよ。
償却解析は入力の運に頼らず、どの順で操作してもならした平均が収まることを示すんだ。平均ケースのような「運がよいとき」の話ではないよ。
選択肢1は関係が逆。選択肢3の「同じ言葉」、選択肢4の「メモリ量」はどちらも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 償却は運に頼らない |
| 2 | ✓ | どの順でもならした平均が収まる |
| 3 | ✗ | 同じ言葉ではない |
| 4 | ✗ | どちらも速さの評価 |
まとめ
押さえどころ
- 🔴 考え方 ＝ 一連の操作を全体でならして、1回あたりの平均の速さを評価する。
- 🔴 動的配列の2倍拡張 ＝ 拡張のときだけ重いが、ならすと償却O(1)。
- 🟡 3手法と平均ケースとの違い ＝ 集計法・会計法・ポテンシャル法。運に頼らずどの順でもならせる保証。
次に学ぶ
執筆: SikakuQuest編集部