目次
「このコードは遅い」と言われたとき、どれくらい遅いか、どう改善できるかを論理的に説明できるだろうか。O記法（ビッグオー記法）は計算量を抽象的に表現する道具で、アルゴリズムの比較と選択の共通言語だ。
O記法とは何か
O記法は「入力サイズ n が増えたとき、処理時間（または空間）がどのくらいの割合で増えるか」を表す。定数倍や低次の項は無視して、増加の「傾向」だけを捉える。
具体的な実行時間: 3n² + 5n + 100 ms
O記法: O(n²)
↑ 最も影響が大きい項のみ残す
なぜ定数を無視するか: nが大きくなれば主要な項が支配的になり、定数は誤差範囲に収まるから。
主要な計算量クラス
O(1)——定数時間
入力サイズに関係なく、常に一定の時間で完了する。
# 配列の要素へのアクセス
def get_element(arr, index):
return arr[index] # O(1): インデックスで直接アクセス
# 辞書の検索
def get_user(users_dict, user_id):
return users_dict.get(user_id) # O(1): ハッシュテーブルで直接アクセス
# スタックの push/pop
from collections import deque
stack = deque()
stack.append(1) # O(1)
stack.pop() # O(1)
O(log n)——対数時間
入力が2倍になるたびに処理ステップが1増える。非常に効率的。
def binary_search(sorted_arr, target):
"""二分探索: O(log n)"""
left, right = 0, len(sorted_arr) - 1
while left <= right:
mid = (left + right) // 2
if sorted_arr[mid] == target:
return mid
elif sorted_arr[mid] < target:
left = mid + 1 # 右半分を探索
else:
right = mid - 1 # 左半分を探索
return -1
# n=1000万でも最大23回の比較で見つかる（log₂(10,000,000) ≈ 23）
arr = list(range(10_000_000))
idx = binary_search(arr, 9_999_999)
print(idx) # 9999999
O(n)——線形時間
入力に比例して処理時間が増える。配列を一度だけ走査するとき。
def find_max(arr):
"""最大値を線形探索: O(n)"""
if not arr:
return None
max_val = arr[0]
for x in arr: # n 回のループ
if x > max_val:
max_val = x
return max_val
def has_duplicate(arr):
"""重複チェック: O(n)（ハッシュセット使用）"""
seen = set()
for x in arr:
if x in seen:
return True
seen.add(x)
return False
# ❌ O(n²) の重複チェック（避けるべき）
def has_duplicate_slow(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] == arr[j]:
return True
return False
O(n log n)——線形対数時間
効率的なソートアルゴリズムがここに入る。
# Python の組み込みソート: Timsort = O(n log n)
arr = [5, 2, 8, 1, 9, 3]
arr.sort()
# マージソートで O(n log n) の仕組みを理解する
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # O(log n) 回の分割
right = merge_sort(arr[mid:])
return merge(left, right) # 各レベルで O(n) のマージ
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
O(n²)——二乗時間
ネストしたループが典型例。入力が2倍になると処理時間が4倍になる。
def bubble_sort(arr):
"""バブルソート: O(n²)"""
n = len(arr)
for i in range(n): # n 回
for j in range(n - i - 1): # 最大 n 回
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# n=10,000 で実行時間を比較
import time
arr = list(range(10000, 0, -1)) # 最悪ケース（逆順）
start = time.time()
sorted(arr) # O(n log n): Timsort
print(f"Timsort: {time.time() - start:.4f}秒") # 約0.001秒
arr2 = list(range(1000, 0, -1)) # n=1000 でのみ試す（n=10000は遅すぎる）
start = time.time()
bubble_sort(arr2)
print(f"バブルソート(n=1000): {time.time() - start:.4f}秒") # 約0.1秒
O(2ⁿ)——指数時間
入力が1増えるたびに処理量が2倍になる。n が30程度でも数十億ステップになる。
def fib_naive(n):
"""素朴なフィボナッチ: O(2ⁿ)"""
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
# fib_naive(30): 約270万回の呼び出し
# fib_naive(50): 約1000億回（現実的でない）
# メモ化でO(n)に改善
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
"""メモ化フィボナッチ: O(n)"""
if n <= 1:
return n
return fib_memo(n - 1) + fib_memo(n - 2)
# または動的プログラミング
def fib_dp(n):
"""動的プログラミング: O(n) 時間・O(1) 空間"""
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
計算量の比較
n=1,000,000 での大まかな処理数：
| O記法 | 処理数 | 実感 |
|---|---|---|
| O(1) | 1 | 即時 |
| O(log n) | 20 | 即時 |
| O(n) | 1,000,000 | 数ms |
| O(n log n) | 20,000,000 | 数十ms |
| O(n²) | 1,000,000,000,000 | 事実上不可能 |
| O(2ⁿ) | 10^300,000 | 宇宙年齢でも終わらない |
空間計算量
時間だけでなく、使用メモリ量（空間計算量）も重要だ。
# O(1) 空間: 追加メモリを使わない
def sum_array(arr):
total = 0 # 定数個の変数のみ
for x in arr:
total += x
return total
# O(n) 空間: 入力と同サイズのメモリを使う
def copy_array(arr):
return list(arr) # n 個の要素をコピー
# 時間と空間のトレードオフ
def fib_dp_time_optimized(n):
# O(n) 時間・O(1) 空間（前の2値のみ保持）
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
def fib_dp_precomputed(max_n):
# O(n) 時間・O(n) 空間（全値をキャッシュ）
dp = [0] * (max_n + 1)
dp[1] = 1
for i in range(2, max_n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp # 全値に O(1) でアクセス可能
実践：N+1問題
データベースアクセスでよく起きる計算量の問題がN+1問題だ。
# ❌ N+1問題: O(n) のDBクエリ
def get_users_with_orders_slow(user_ids):
users = db.query("SELECT * FROM users WHERE id IN ?", user_ids) # 1クエリ
for user in users:
# ユーザーごとに1クエリ → N ユーザーで N+1 クエリ
user.orders = db.query("SELECT * FROM orders WHERE user_id = ?", user.id)
return users
# ✅ 一括取得: O(1) クエリ（データ量はO(n)だが）
def get_users_with_orders_fast(user_ids):
users = db.query("SELECT * FROM users WHERE id IN ?", user_ids)
# 全ユーザーのIDを使って注文を一括取得
orders = db.query(
"SELECT * FROM orders WHERE user_id IN ?",
[u.id for u in users]
)
# Pythonでインメモリ結合
orders_by_user = {}
for order in orders:
orders_by_user.setdefault(order.user_id, []).append(order)
for user in users:
user.orders = orders_by_user.get(user.id, [])
return users
計算量改善のチェックリスト
□ ネストしたループを発見したら: O(n²) → O(n) に改善できないか？
→ ハッシュマップで外側ループの内側を O(1) に
→ ソート + 二分探索で O(n²) → O(n log n) に
□ ソートが必要か確認:
→ 「最小/最大」だけなら O(n) の線形探索で十分
→ ソートは O(n log n) のコストがかかる
□ 繰り返し同じ計算をしていないか:
→ メモ化（lru_cache）やDP表で O(n) に削減
□ 適切なデータ構造を選べているか:
→ 検索多い: dict/set（O(1)）vs list（O(n)）
→ ソート済みを前提: heapq（O(log n)）
まとめ
O記法はコードのパフォーマンスを語る共通言語だ。「このコードはO(n²)だから、n=10万で問題になる」という判断ができるようになることが目標だ。
- O(1): 定数時間——ハッシュマップ・配列インデックス
- O(log n): 対数時間——二分探索・平衡二分木
- O(n): 線形時間——線形探索・ハッシュセットによる重複確認
- O(n log n): 線形対数時間——効率的なソート（Timsort・マージソート）
- O(n²): 二乗時間——ネストループ・バブルソート（n > 10万で問題）
- O(2ⁿ): 指数時間——ほぼ使えない。DP・メモ化で改善必須
- N+1問題: DBアクセスパターンで頻発するO(n)クエリ問題
「計算量を把握してからコードを書く」習慣が身につくと、後からリファクタリングが必要になる場面を大幅に減らせる。
免責事項 — 掲載情報は執筆時点のものです。料金・機能は変更される場合があります。最新情報は各公式サイトをご確認ください。