Big-O記法 — パフォーマンスを数値で表現する

このトピックを終えると

Big-O記法が何であるかを理解し、コードを見て時間計算量を推定できるようになり、O(1) / O(n) / O(n²) / O(log n)の違いを説明できるようになります。

Big-Oが必要な理由

「このコードは遅い」— どの程度遅いのか、データが増えるとどの程度遅くなるのかを説明できる必要があります。Big-Oは、入力サイズ（n）に応じて演算回数がどのように増加するかを表現する記法です。

実行時間を秒単位で測定するものではありません。コンピュータの性能によって秒単位は異なるからです。Big-Oは、増加パターンを指します。

O(1) — 定数時間

入力サイズに関係なく、常に同じ時間がかかります。

def get_first(items):
    return items[0]  # 100個でも100万個でも1回

# 辞書の参照もO(1)
user = {"name": "キム・フン"}
user["name"]  # ハッシュ計算 → すぐにアクセス

データが10倍に増えても、時間は変わりません。

O(n) — 線形時間

入力サイズに比例して、時間が長くなります。

def find_max(items):
    max_val = items[0]
    for item in items:      # n回繰り返す
        if item > max_val:
            max_val = item
    return max_val

リストが100個なら100回、100万個なら100万回比較します。データが10倍に増えると、時間も10倍に増えます。forループが1つだけでリスト全体を走査する場合、通常はO(n)です。

O(n²) — 二乗時間

ネストされたループが代表的です。

def has_duplicate(items):
    for i in range(len(items)):         # n回
        for j in range(i + 1, len(items)):  # 最大n回
            if items[i] == items[j]:
                return True
    return False

100個なら約5,000回、1,000個なら約500,000回、10,000個なら約50,000,000回です。データが10倍に増えると、時間が100倍に増えます。これがO(n²)が危険な理由です。

# O(n)で改善 — setを活用
def has_duplicate_fast(items):
    seen = set()
    for item in items:       # n回
        if item in seen:     # set検索 O(1)
            return True
        seen.add(item)
    return False

同じ問題をO(n)で解決すると、10,000個の場合、50,000,000回だったものが10,000回に減ります。

O(log n) — 対数時間

各ステップで、検索範囲が半分に減少します。二分探索が代表的です。

def binary_search(sorted_list, target):
    low, high = 0, len(sorted_list) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if sorted_list[mid] == target:
            return mid
        elif sorted_list[mid] < target:
            low = mid + 1        # 左側の半分を捨てる
        else:
            high = mid - 1       # 右側の半分を捨てる
    
    return -1  # 見つからない

100万個の場合、最大20回比較で見つけられます（log₂(1,000,000) ≈ 20）。O(n)なら100万回ですが、O(log n)なら20回です。ただし、ソートされたデータでのみ機能します。

一目で比較

O(n²)は、nが10,000を超えると実用的ではありません。O(n log n)は、効率的なソートアルゴリズム（マージソート、クイックソート）の複雑度です。

Big-Oを読むための重要なルール

1. 定数は捨てる: O(3n) = O(n), O(100) = O(1)
2. 低い次数は捨てる: O(n² + n) = O(n²) — nが大きい場合、n²がnを圧倒する
3. 最悪の場合を考慮する: リストで検索する場合、最初に見つかればO(1)ですが、Big-Oは最後に存在する最悪の場合を基準にO(n)とします。

この3つのルールがあれば、ほとんどのコードでBig-Oを推定できます。

重要なまとめ

Big-Oは、「このコードがデータが10倍になっても生き残れるか」を判断するためのツールです。完璧な計算よりも、パターンを認識することが重要です。forが1つならO(n)、ネストされたforならO(n²)、半分ずつ減少したらO(log n)。面接でよく聞かれるテーマですが、それ以上に、実際の問題で「なぜこのAPIがデータ量が多いと遅くなるのか」の原因を突き止めるのに直接役立ちます。