ビッグO記法と計算量

アルゴリズムの「速さ」を測る

コードが「なんとなく動く」から「なぜ速い/遅いかわかる」へ。その第一歩がビッグO記法（Big-O Notation）です。

ビッグO記法は入力サイズ n が増えたときに、処理時間（または使用メモリ）がどのように増えるかを表します。定数倍の違いは無視して、増加の傾向だけを見ます。

主要なオーダーの一覧

n=1,000 のとき、O(n²) は O(n log n) の約100倍の処理量になります。

O(1) — 定数時間

入力サイズに関係なく常に同じ時間で処理が終わります。

def get_first(arr):
    return arr[0]  # 配列が100万件でも1件でも同じ

def has_key(d, key):
    return key in d  # ハッシュマップの検索はO(1)

ハッシュマップ（Python の dict、JavaScript の Map）の検索・挿入・削除は平均 O(1) です。

O(log n) — 対数時間

二分探索が代表例です。1回の比較のたびに探索範囲が半分になります。

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

n=1,000,000 でも最大10回の比較で済みます（log₂(1,000,000) ≈ 20）。

O(n) — 線形時間

配列を先頭から末尾まで1回舐める処理が典型です。

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

def find_max(arr):
    max_val = arr[0]
    for val in arr:         # n 回ループ
        if val > max_val:
            max_val = val
    return max_val

O(n log n) — 線形対数時間

効率的なソートアルゴリズム（マージソート・クイックソート）のオーダーです。O(n²) のソートより圧倒的に速く、実用上ほとんどのソートはこのオーダーです。

sorted_arr = sorted(arr)        # Python の組み込みソートは O(n log n)
arr.sort()                       # 同じく O(n log n)

O(n²) — 二乗時間

ネストしたループが典型。n が大きくなると急激に遅くなります。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):         # 外側ループ: n 回
        for j in range(n - i - 1):   # 内側ループ: n 回（合計 n²）
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

n=10,000 のバブルソートは n=1,000 より 100倍遅くなります。

O(2ⁿ) — 指数時間

ナイーブな再帰的フィボナッチが典型。n=50 でも宇宙の寿命より長い時間がかかります。

def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)  # 指数的に再帰が増加

def fib_dp(n, memo={}):           # メモ化でO(n)に改善
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_dp(n - 1, memo) + fib_dp(n - 2, memo)
    return memo[n]

空間計算量

計算量には時間だけでなく**空間（メモリ使用量）**もあります。

def double(arr):
    return [x * 2 for x in arr]   # 空間O(n): 新配列を作る

def double_inplace(arr):
    for i in range(len(arr)):     # 空間O(1): 元の配列を書き換え
        arr[i] *= 2

計算量の見極め方

1. ループの深さを確認する
   - 1重ループ → O(n)
   - 2重ループ → O(n²)
   - 毎回半分になる → O(log n)

2. 定数は無視する
   - 3n + 5 → O(n)
   - 2n² + n → O(n²)

3. 最大項だけ残す
   - O(n² + n) → O(n²)
   - O(n log n + n) → O(n log n)

まとめ

計算量を理解すると、「なぜこのコードは遅いのか」が論理的に説明できるようになります。