階乗時間 O(n!) — 最も扱いにくい計算量
最も極端な一般的計算量クラスであるO(n!)階乗時間計算量を探求します。順列問題がこれほど速く成長する理由と、近似が唯一の選択肢である場合を理解します。
Complexity Classes
詳細な説明
O(n!)階乗時間とは？
O(n!)は、操作数が入力サイズの階乗に等しい計算量クラスです。n! = n × (n-1) × ... × 1。
成長率
| n | n! |
|---|---|
| 5 | 120 |
| 10 | 3,628,800 |
| 15 | 1,307,674,368,000 |
| 20 | 2,432,902,008,176,640,000 |
典型的なO(n!)アルゴリズム
巡回セールスマン問題（総当たり） — n都市を正確に1回ずつ訪問する最短ルートを全探索。
全順列生成 — n個の要素のあらゆる順序をリスト。
実用的な解決策
- 動的計画法 + ビットマスク: TSPはHeld-KarpでO(n² × 2ⁿ)に削減可能
- 近似アルゴリズム: ChristofidesのアルゴリズムはメトリックTSPと1.5倍近似
- メタヒューリスティクス: 大規模インスタンス向け
ユースケース
階乗計算量の理解は、問題が計算的に扱いにくい場合を認識し、正確な総当たり解法ではなく近似アルゴリズム、ヒューリスティクス、または制約削減を使用する必要がある場合に役立ちます。