女性向けエンジニアスクール
3秒でわかる
入力が増えたとき処理時間やメモリがどう伸びるかを、定数を捨てて表す記法。アルゴリズムを実測せずに比べるための共通のものさしです。
もう少し詳しく
どういうものか
ビッグO記法は、入力の大きさ n が大きくなったときに、アルゴリズムの実行時間やメモリ使用量が どのくらいの勢いで増えるか だけを取り出して書く書き方です。O(n) なら n に比例、O(n^2) なら n の 2 乗に比例して増えます。
特徴は、細かい部分を意図的に捨てることです。実際の手順数が 3n + 50 でも、係数の 3 も定数の 50 も落として O(n) と書きます。n が十分大きくなれば、増え方を決めるのは一番強い項だけだからです。
なぜ必要か
同じ処理でも、実行時間は CPU の速さ、言語、その日のマシンの混み具合で変わります。手元で 0.2 秒だったから速い、という比較は環境が変わると通用しません。
ビッグO記法は「入力が 10 倍になったら何倍になるか」を表すので、環境に左右されません。O(n) は 10 倍、O(n^2) は 100 倍、O(log n) はほとんど増えない。この一言で、データが 100 万件に増えた将来の姿まで議論できます。
具体例
def linear_search(arr, target):
for i, v in enumerate(arr): # O(n)
if v == target:
return i
return -1
def binary_search(sorted_arr, target):
lo, hi = 0, len(sorted_arr) - 1
while lo <= hi: # O(log n)
mid = (lo + hi) // 2
if sorted_arr[mid] == target:
return mid
if sorted_arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1要素 100 万件のとき、線形探索は最悪 100 万回の比較、二分探索は 20 回で終わります。
つまずきやすいところ
O(n^2) だと思い込む — 内側のループ回数が入力と無関係な定数（たとえば常に 3 回）なら O(n) ですO(n) でも、1 件ごとに DB へ問い合わせる O(n) はメモリ上の O(n) より桁違いに遅くなります。n が小さい実務では定数が勝負を決めますO(n log n)、最悪 O(n^2) です。どちらの話をしているかを先に決めます似た用語との違い
| 記法 | 表すもの | 使いどころ |
|---|---|---|
| O | 上界。これより悪くはならない | ほぼ全ての実務の会話 |
| Ω | 下界。少なくともこれだけかかる | 理論的な限界の証明 |
| Θ | 上下が一致する厳密な評価 | 論文や試験の厳密な記述 |
覚え方
O は「多く見積もってもここまで」の O と覚えます。速い順に O(1)、O(log n)、O(n)、O(n log n)、O(n^2)、O(2^n) の 6 段を暗記しておくと、コードを読んだ瞬間に当てはめられます。
