最終更新: 2026-06-23

ビッグO記法の増加率

ビッグO記法は、アルゴリズムのリソース消費が入力サイズに対してどのように拡大するかを分類する記法です。特定のマシンで何秒かかるかを測るのではなく、増加の形状を捉えます。n が 2 倍になったとき、処理量も 2 倍になるのか、それとも 4 倍になるのか。以下の 6 つの計算量クラスは、教科書や技術面接で最もよく登場するものです。

6 つの代表的な計算量クラス

O(log n) — 対数時間。 各ステップで残りの処理の一定割合が除去されます。10 億件の要素を持つソート済み配列に対する二分探索は、毎回探索範囲を半分に絞り込むため、比較は 30 回で済みます。平衡 BST の検索や、多くの分割統治アルゴリズムの再帰がここに該当します。

O(n) — 線形時間。 処理量が入力サイズに正比例して増加します。配列を一度走査して最大値を求める線形探索、文字列の文字数カウント、リストの全要素の読み取りなどが該当します。線形時間アルゴリズムは一般に効率的とみなされます。

O(n log n) — 準線形時間。 ソートで最もよく見られる計算量です。マージソート、ヒープソート、Python と Java で採用されている Timsort はいずれも O(n log n) を達成しており、これは比較ベースのソートの理論的下限でもあります。$n = 10^6$ の場合、演算数はおよそ 2,000 万回であり、実用的には十分高速です。

O(n²) — 二乗時間。 入力に対する二重ループ。バブルソート、挿入ソート、素朴な行列積はいずれも最悪ケースで O(n²) です。$n = 10^4$ では 1 億回、$n = 10^6$ では 1 兆回となり、大量データには不向きです。

O(2ⁿ) — 指数時間。 要素が 1 つ増えるごとに処理量が 2 倍になります。再帰的なフィボナッチの素朴な実装は部分問題を指数的に再計算し、集合の部分集合を全列挙するブルートフォースも $2^n$ で増加します。n = 40 で演算数は 1 兆を超えます。

O(n!) — 階乗時間。 日常的なアルゴリズム解析で最も急速に増加するクラスです。巡回セールスマン問題への総当たり解法は考えられるすべての経路（順列）を調べ、その総数は $n!$ 通りになります。n = 20 の時点で演算数は 200 京を超えます。

n = 20 での計算例

$\log_2 20 \approx 4.32 \quad\quad 20 \quad\quad 20 \log_2 20 \approx 86.4$

$20^2 = 400 \quad\quad 2^{20} = 1{,}048{,}576 \quad\quad 20! \approx 2.43 \times 10^{18}$

n = 20 における O(n log n) と O(n!) の比はおよそ $10^{16}$ 倍です。高速なソートと宇宙の年齢よりも長い待ち時間の差と言えます。

実践的な指針

n が小さいうちは定数係数とキャッシュ効率が重要ですが、n が大きくなると計算量が支配的になります。おおよそ n = 10,000 を境に、O(n²) は現代のハードウェアでも（単純な演算を想定した場合）扱いにくくなり始めます。n が $10^6$ を超えると、O(n log n) 以上に優れたアルゴリズムが実質的に必須となります。指数時間・階乗時間のアルゴリズムは、実世界の入力に対しては近似アルゴリズム、動的計画法、または枝刈り戦略が必要です。

基数変換ツール は、入力空間の二進表現を扱う際に役立ちます。