計算量（O記法）
まず結論
O記法（ビッグO記法）はアルゴリズムの「データ量nが増えたとき処理時間がどう増えるか」を表します。速い順にO(1) < O(log n) < O(n) < O(n log n) < O(n²)。
各O記法の意味と例
O(1) 定数
配列のインデックスアクセス a[5]
O(log n)
二分探索（1024要素→10回）
O(n) 線形
線形探索（n個を1つずつ確認）
O(n log n)
クイックソート・マージソート（平均）
O(n²) 二乗
バブルソート・選択ソート・2重ループ
←高速 バーの長さ = 処理時間（n=1000の場合） 低速→
具体的な数字で比較
| オーダー | n=10 | n=100 | n=1,000 | n=1,000,000 |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 1 |
| O(log n) | 3 | 7 | 10 | 20 |
| O(n) | 10 | 100 | 1,000 | 1,000,000 |
| O(n log n) | 33 | 664 | 10,000 | 20,000,000 |
| O(n²) | 100 | 10,000 | 1,000,000 | 10¹²（≒30年） |
O(n²)の恐ろしさ：nが10倍になると処理時間が100倍に。n=100万のO(n²)アルゴリズムは現実的に使えない。
O記法の読み取り方
O(1) を見つける
nに無関係な定数回の処理。
配列アクセス・スタックpush/pop・ハッシュ参照など。
O(n) を見つける
配列を1度だけ全走査するループ。for i in 1..nのような1重ループ。
O(n²) を見つける
2重ループ（ループの中にループ）。
バブルソートの2重for文が典型例。
O(log n) を見つける
毎回探索範囲が半分になる処理。
二分探索・BST操作が典型例。
定数係数は無視する：O(2n)もO(3n)もどちらもO(n)と表記。nが大きくなると定数の差は相対的に無視できる。
🎯 試験での出方
- 「二重ループのアルゴリズムの計算量」→ O(n²)
- 「二分探索の計算量」→ O(log n)
- 「ある操作の計算量を選ぶ問題」→ ループ構造を見てO記法を判断
- ソートアルゴリズムの計算量比較（バブル:O(n²)、マージ:O(n log n)）
⚠️ よくある間違い
- 「O(2n)はO(n²)」→ ✗ O(2n) = O(n)（定数係数は無視）
- 「O(n log n)はO(n²)より速い」→ ✓ O(n log n) < O(n²) なので正しい
- 「O(1)は処理が1回だけ」→ ✗ 定数回（100回でも固定回数なら）O(1)
✍️ 確認クイズ
Q1. n個の要素に対して2重ループ（ループの中にループ）を実行する場合の計算量はどれか。
✅ 正解は③。2重ループはn×n=n²回の処理になるのでO(n²)。バブルソートが典型例です。
Q2. 計算量が最も小さい（最も高速な）ものはどれか。
✅ 正解は②。速い順は O(1) < O(log n) < O(n) < O(n log n) < O(n²)。O(log n)が最も速い（O(1)は選択肢なし）。
Q3. 配列の特定インデックスへのアクセス（a[5]など）の計算量はどれか。
✅ 正解は①。配列はインデックスから直接アドレスを計算してアクセスするためO(1)（定数時間）です。要素数nに関係なく一定時間でアクセスできます。
Q4. 平均計算量O(n log n)のソートアルゴリズムはどれか。
✅ 正解は②。クイックソートの平均計算量はO(n log n)です。マージソートも常にO(n log n)。バブルソートはO(n²)。線形探索はソートではなく探索アルゴリズムでO(n)です。試験では「O(n log n)のソート = クイックソート or マージソート」と覚えましょう。
Q5. 次の2重ループの計算量はどれか。「i を 1〜n 繰り返す：j を 1〜n 繰り返す：処理」
✅ 正解は②。2重ループ（外側n回×内側n回）は合計n²回の処理が実行されるためO(n²)。バブルソートの「全ての隣接ペアを比較する」操作が2重ループになっているため、O(n²)になります。ループが1つ増えるたびに次数が1上がります（3重ループ→O(n³)）。
Sponsor Link