アルゴリズムの計算量とO記法
1. 概要
A. 定義
アルゴリズムの計算量(complexity) とは、入力サイズ(n)に応じてアルゴリズムが消費する資源の量であり、演算回数を測る 時間計算量 とメモリを測る 空間計算量 に区分される。O記法(ビッグオー) は、入力が十分に大きくなったときの 増加率(漸近的上界、asymptotic upper bound) を表記する方法である。
計算量を実際の実行時間(秒)ではなく 演算回数の増加率 で測定する理由が重要である。実行時間はCPU性能・言語・コンパイラによって変わるため、アルゴリズムそのものの優劣を判断できないが、「入力が2倍になると演算は何倍になるか」はハードウェアに依存しない アルゴリズム固有の性質 だからである。そのためO記法は定数項・低次項を切り捨て、最も支配的な項の増加率 だけを残す — たとえば3n²+5n+7は、nが大きくなるとn²の項が支配的になるためO(n²)と表記する。
B. 漸近記法の種類
Oだけがあるわけではなく、上界・下界・厳密な限界をそれぞれ表す3つの記号がある。実務では 最悪ケースを保証 することが設計の安全性の観点から重要であるため、上界を表す O が最も広く使われる。
| 表記 | 意味 | 観点 |
|---|---|---|
| O (ビッグオー) | 漸近的上界 | 最悪(worst) — 性能保証 |
| Ω (ビッグオメガ) | 漸近的下界 | 最良(best) |
| Θ (ビッグシータ) | 上界・下界が一致 | 厳密な増加率(average) |
2. O記法の類型と演算量
以下のグラフは、入力サイズnが大きくなるにつれて各計算量の演算量がどのように開いていくかを示している。nが小さいうちは差はわずかだが、nが大きくなるとO(n²)以上は急激に発散し、事実上実行不可能になる。まさにこの 大きなnにおける差 がアルゴリズムの選択を左右する。
{
"type": "line",
"data": {
"labels": ["1","2","4","8","16","32","64"],
"datasets": [
{ "label": "O(1)", "data": [1,1,1,1,1,1,1], "borderColor": "#0e9f6e", "tension": 0.2 },
{ "label": "O(log n)", "data": [0,1,2,3,4,5,6], "borderColor": "#2f6fed", "tension": 0.2 },
{ "label": "O(n)", "data": [1,2,4,8,16,32,64], "borderColor": "#f59e0b", "tension": 0.2 },
{ "label": "O(n log n)", "data": [0,2,8,24,64,160,384], "borderColor": "#8b5cf6", "tension": 0.2 },
{ "label": "O(n^2)", "data": [1,4,16,64,256,1024,4096], "borderColor": "#e11d48", "tension": 0.2 }
]
},
"options": {
"plugins": { "legend": { "position": "bottom" }, "title": { "display": true, "text": "入力サイズ(n)に対する演算量の増加" } },
"scales": { "y": { "title": { "display": true, "text": "演算回数" } } }
}
}
各類型はアルゴリズムの 動作構造 に由来する。なぜその計算量になるのかを理解すれば、コードを見るだけで計算量を見積もることができる。
- O(1) 定数: 入力サイズに関係なく一定の演算。ハッシュ参照・配列インデックスアクセスのように 一度で位置を計算 する場合である。
- O(log n) 対数: 各ステップごとに 探索範囲を半分に 縮める構造。二分探索が代表的であり、nが百万でも約20回で終わる。
- O(n) 線形: 入力を 一度走査する 構造。逐次探索・合計計算がこれにあたる。
- O(n log n) 線形対数: データを分割したうえで(log n段階)各段階で全体を走査する(n)構造。マージソート・クイックソートのような 効率的なソート の下限である。
- O(n²) 二乗: 二重ループ ですべてのペアを比較する構造。バブルソート・挿入ソートが該当し、nが大きくなると急激に遅くなる。
- O(2ⁿ) 指数: 各ステップで場合の数が 2倍に分岐 する構造。メモ化なしの再帰フィボナッチ・部分集合の列挙がこれにあたる。
- O(n!) 階乗: すべての 順列 を試す構造。巡回セールスマン問題(TSP)の全探索が代表であり、n=20になるだけで計算不可能である。
| 類型 | 名称 | 構造原理 | 例 |
|---|---|---|---|
| O(1) | 定数 | 直接アクセス | ハッシュ参照、配列インデックス |
| O(log n) | 対数 | 範囲を半分ずつ縮小 | 二分探索 |
| O(n) | 線形 | 一度走査 | 逐次探索 |
| O(n log n) | 線形対数 | 分割+走査 | マージ・クイックソート |
| O(n²) | 二乗 | 二重ループ(全ペア) | バブル・挿入ソート |
| O(2ⁿ) | 指数 | 2倍ずつ分岐 | 部分集合、再帰フィボナッチ |
| O(n!) | 階乗 | 全順列 | 巡回セールスマン全探索 |
増加率: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
3. ケース分析
同じアルゴリズムでも入力の状態によって性能が変わるため、最良・平均・最悪を区別して分析する。たとえば クイックソート は、ピボットが毎回中央値に近ければ平均O(n log n)であるが、すでにソート済みの配列でピボットを誤って選ぶと分割が一方に偏り 最悪O(n²) となる。設計では通常 最悪ケース(O) を基準にしてこそ、本番サービスでの性能が保証される。
| ケース | 表記 | 意味 |
|---|---|---|
| 最良(Best) | Ω | 最も速い入力での性能 |
| 平均(Average) | Θ | 期待性能 |
| 最悪(Worst) | O | 保証上界 — 設計基準 |
4. 考慮事項および示唆
- 大きなnでは計算量が性能を支配: 小規模データでは定数の差が大きく、O(n²)がO(n log n)より速いこともありうるが、大容量データでは漸近計算量が絶対的である。データ規模に合ったアルゴリズムの選択が鍵である。
- 時間・空間のトレードオフ: 計算量は時間と空間の間で交換される。たとえば キャッシング・メモ化 はメモリ(空間)を多く使うことで反復計算(時間)を減らす — 再帰フィボナッチをメモ化するとO(2ⁿ)がO(n)に減るのが代表例である。
- 漸近解析の限界の補完: 定数項・ハードウェア・キャッシュ局所性・定数倍は無視されるため、実際のチューニング時にはプロファイリングによる実測を併用する。
- 連携・展望: 多項式時間(P)で解けるか否かは P-NPなど計算複雑性理論 の中心テーマであり、TSPのようにO(n!)となるNP困難問題は 近似・ヒューリスティック・動的計画法 で現実的な解を求める。計算量分析はアルゴリズム選択・最適化の基本的な尺度である。
一言まとめ: O記法は入力サイズに応じたアルゴリズムの 最悪増加率(漸近上界) をハードウェアに依存せず表記するものであり、O(1)→O(log n)→O(n)→O(n log n)→O(n²)→O(2ⁿ)→O(n!) の順に性能が急激に悪化するため、時間・空間トレードオフと大きなnでの支配性を考慮してアルゴリズムを選択する。