指数時間 O(2ⁿ) — 問題が爆発するとき
O(2ⁿ)指数時間計算量を理解し、問題を扱いにくくする理由、動的計画法とメモ化が指数アルゴリズムを救える方法を学びます。
Complexity Classes
詳細な説明
O(2ⁿ)指数時間とは？
アルゴリズムがO(2ⁿ)とは、入力の各追加要素で操作数が倍増することを意味します。
成長率
| n | 2ⁿ |
|---|---|
| 10 | 1,024 |
| 20 | 1,048,576 |
| 30 | 1,073,741,824 |
| 40 | ~1.1兆 |
典型的なO(2ⁿ)問題
- ナイーブFibonacci再帰 — メモ化なしでは冗長な呼び出しが指数的に増加
- 冪集合生成 — n要素の集合のす2ⁿ個の部分集合を生成
- 部分和問題（総当たり） — ターゲットに合計する部分集合を全探索
- ハノイの塔 — n枚のディスクの移動に2ⁿ - 1回の移動が必要
脱出経路
- 動的計画法: FibonacciはO(2ⁿ)からO(n)に削減可能
- 分枝限定法: 探索木の枝を切り落とす
- 近似アルゴリズム: 多項式時間で準最適解を受け入れる
ユースケース
指数計算量の認識は、NP困難問題を理解し、総当たりから動的計画法、近似、ヒューリスティクスへの切り替えタイミングを知るために不可欠です。