計算量オーダー——速さの言い方

実時間ではなく「入力サイズへの増加率」でアルゴリズムを比較する。

この単元の目標

O記法でアルゴリズムの増加率を表せる
代表的なソートの計算量を比較できる
多項式時間と指数時間の違い、実用性を判断する際の注意点を説明できる

📑 目次

なぜオーダーで語るのか
代表例
ループの形から処理回数を数える

なぜオーダーで語るのか

同じコードでもマシンや言語で絶対時間は変わります。そこで入力サイズ n に対する処理回数の増え方を比較します。ビッグオー $O(f(n))$ は漸近的な上界であり、十分大きな n で処理回数が定数倍の f(n) 以下になることを表します。増加率が上下とも定数倍で一致するときは $\Theta(f(n))$ と書きます。O 記法だけでは実時間や正確な回数比は決まりません。以下の表は、代表的な増加項を係数 1 として代入した目安です。

オーダー	名前	n = 1000 での目安
$O(1)$	定数	入力サイズによらず一定（速いとは限らない）
$O(\log n)$	対数	約 10 ステップ（二分探索）
$O(n)$	線形	1000 ステップ（全走査）
$O(n \log n)$	線形対数	約 10⁴（高速ソート）
$O(n^2)$	二乗	10⁶（単純ソート）
$O(2^n)$	指数	約 10³⁰¹（部分集合の全列挙）

代表例

二分探索: ソート済み配列なら $O(\log n)$ 。1 回の比較で候補が半分になる
マージソート: 最悪でも $O(n \log n)$ 。クイックソート: 平均 $O(n \log n)$ 、最悪 $O(n^2)$ 。比較だけで任意の入力を整列する場合、最悪比較回数には $\Omega(n \log n)$ の下界がある
バブルソート: $O(n^2)$ 。遅いが理解しやすい
動的計画法: 部分問題の答えを表に保存して重複計算を消す（フィボナッチで $O(2^n) \to O(n)$ ）。ここでは各加算を一定時間と数える。大きな整数の桁数まで考えるビット計算量とは区別する

例題

処理回数をそれぞれ $n^2$ 回、 $n \log_2 n$ 回と仮定する。n = 1024 のときの比は何倍か。

解答・解説

$1024^2 = 1048576$ 、 $1024 \times 10 = 10240$ 。比は **102.4 倍**。係数や実装が異なる実時間の比を O 記法だけから断定することはできない。

ループの形から処理回数を数える

ループが二重でも、必ず n² 回とは限りません。内側の回数が外側の変数に依存するなら、各回の回数を足します。また i を 2 倍ずつ増やすループでは、k 回後に i = 2ᵏ となるので、終了条件から対数が現れます。多項式時間も n¹⁰⁰ のように実用困難な場合があり、「多項式なら必ず速い」わけではありません。

例題：三角形に増える繰り返し

i = 1, 2, …, n の各回で、内側の処理を i 回ずつ実行する。総回数と増加率を求めよ。

解答・解説

$1+2+\cdots+n=n(n+1)/2$ 回。n = 4 なら 10 回で、n² = 16 回とは異なるが、最高次項は n²/2 なので増加率は $\Theta(n^2)$ （したがって $O(n^2)$ ）である。

練習問題

次のコードのオーダーを答えよ。 ``` for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) sum++; } ```
解答・解説
$O(n^2)$ 。内側のループが n 回 × 外側が n 回。
辞書で単語を探すとき、ページを端からめくる方法と中央を開いて絞り込む方法のオーダーは？
ヒント
後者は二分探索そのもの。
解答・解説
端からは $O(n)$ 、中央から絞り込む方式は $O(\log n)$ 。1000 ページでも後者は 10 回程度の手間。
処理時間が $c2^n$ （c は一定）であるアルゴリズムで n を 10 増やすと何倍になるか。
解答・解説
$2^{10} =$ **1024 倍**。指数時間は入力サイズに対して爆発する。
i = 1 から始め、i < n の間、i を 2 倍する。n = 1024 のときの反復回数と、一般の n に対するオーダーを求めよ。
ヒント
k 回後の値 2ᵏ が初めて n 以上になる条件を考える。
解答・解説
10 回後に 2¹⁰ = 1024 となり終了する。一般に n ≥ 2 で反復回数は $\lceil\log_2 n\rceil$ 、オーダーは $O(\log n)$ 。

確認クイズ（計算量）

問1. 値の比較と任意位置への一定時間アクセスを使い、ソート済み配列を探索する適切な方法と最悪計算量は？

問2. フィボナッチ数列を素朴な再帰で計算するときのオーダーは？

問3. 「多項式時間で解ける」ことが意味するのは？

📝 メモこの端末のみに保存

メモ欄はページ読み込み後に使えるようになります。