アルゴリズムと計算量（Big-O記法）を直感で理解する ── O(1)・O(log n)・O(n)・O(n²) が体でわかる

「ArrayList のインデックスアクセスは速い、LinkedList のインデックスアクセスは遅い」という話は聞いたことがある。でも「どのくらい遅いか」「どれだけデータが増えると問題になるか」を感覚で掴んでいる人は少ない。

それを表現するのが Big-O 記法（計算量） だ。コードを書く上で「これはまずい」と直感できるようになるための最低限の知識を整理する。

1. Big-O とは「データが増えたとき、どう遅くなるか」

Big-O は「アルゴリズムの速度」を表すのではなく、「データ量 n が増えたとき、処理ステップ数がどう増えるか」の比率を表す。

実行時間は CPU の速度・実装・環境に依存するが、「データが 10 倍になったとき何倍遅くなるか」はアルゴリズムの性質で決まる。

2. O(1) ── どれだけデータが増えても同じ速さ

int[] arr = new int[1000000];
System.out.println(arr[500000]); // O(1)

配列のインデックスアクセスは、先頭アドレス + index × サイズ の計算だけでアドレスが出る。1 件でも 100 万件でも同じ 1 ステップ。

HashMap の get・put も（衝突がなければ）O(1) だ。ハッシュ値からバケットを直接特定できる。

件数が 10 倍になっても: 処理時間は変わらない

n=100:       ■
n=1,000:     ■
n=1,000,000: ■  （同じ）

3. O(log n) ── 件数が倍になっても 1 ステップ増えるだけ

二分探索が典型例だ。ソート済みのデータから目的の値を探すとき、毎回「残りの半分」に絞っていく。

// ソート済み配列から binary search
int idx = Arrays.binarySearch(sortedArray, target);

1000 件から探す:
  → 500 件に絞る
  → 250 件に絞る
  → 125 件に絞る
  → ...
  → 10 回程度で見つかる（2^10 = 1024）

1,000,000 件から探す:
  → 20 回程度で見つかる（2^20 ≒ 100万）

件数が 1000 倍（1000→100万）になっても、ステップ数は 10→20（2 倍）にしかならない。

TreeMap・TreeSet の検索・挿入も O(log n) だ（内部が赤黒木）。

n=1,000:     ■■■■■■■■■■
n=1,000,000: ■■■■■■■■■■■■■■■■■■■■

4. O(n) ── 件数に比例して遅くなる

// リストを全部見る
for (String s : list) { // O(n)
    if (s.equals("target")) return s;
}

1 件ずつ確認するしかない。100 万件あれば最悪 100 万回確認する。

LinkedList の get(index) も O(n) だ。先頭から index 回 next を辿るしかない。

n=1,000:     ■■■■■■■■■■
n=10,000:    ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
n=1,000,000: 100倍の時間

5. O(n²) ── 件数の二乗で遅くなる。二重ループに要注意

// 二重ループ
for (int i = 0; i < list.size(); i++) {       // n 回
    for (int j = 0; j < list.size(); j++) {   // × n 回
        if (list.get(i).equals(list.get(j))) { ... }
    }
}

件数が 10 倍になると、処理時間は 100 倍になる。

n=100:      10,000 ステップ
n=1,000:    1,000,000 ステップ（100倍）
n=10,000:   100,000,000 ステップ（さらに100倍）

実務で「突然本番が遅くなった」のはデータ量が増えて O(n²) の箇所が爆発したケースが多い。

6. 比較してみる

n=100 ではどれも大差ない。n=1,000,000 になると O(1) と O(n²) の差は 100 万倍になる。

「件数が少ない間は動いていたが、データが増えたら急に遅くなった」は O(n²) または O(n) のアルゴリズムを O(n) が小さい時に見逃したケースだ。

7. Java のコレクションを Big-O で見直す

※ ArrayList は稀にリサイズで O(n)。HashMap は衝突がない前提。

8. 「ループの中でコレクション操作」は要注意

// ❌ O(n²): ループの中で contains を使っている
List<String> result = new ArrayList<>();
for (String s : bigList) {          // O(n)
    if (!result.contains(s)) {       // O(n) ← ここが線形探索
        result.add(s);
    }
}

// ✅ O(n): Set を使う
Set<String> seen = new HashSet<>();
List<String> result = new ArrayList<>();
for (String s : bigList) {           // O(n)
    if (seen.add(s)) {               // O(1) ← HashSet.add は O(1)
        result.add(s);
    }
}

List.contains() は線形探索（O(n)）だ。ループの中で使うと合計 O(n²)。HashSet.contains() は O(1) なので合計 O(n) に改善できる。

まとめ

「このコードは n が大きくなったとき大丈夫か？」という問いを習慣にするだけで、本番で爆発するコードを事前に防げるようになる。