実践Big-O：数学の不安なしの計算量

はじめに — Big-O がもたらす不安
O() が実際に意味するもの
よく出る計算量クラス
定数が勝つとき — 小さな n とキャッシュ
潜む O(n²) — ネストしたループと N+1 クエリ
空間計算量も忘れずに
償却 — 動的配列の秘密
いつ最適化をやめるべきか
おわりに
参考資料

はじめに — Big-O がもたらす不安

Big-O という言葉を聞くと、大学時代の極限や証明を思い出して身構える人が多いものです。しかし実務での Big-O は試験問題ではなく、直感の道具 です。「入力が10倍に増えたら、このコードはどれだけ遅くなるか？」という、とても実用的な問いに答えるためのものです。

この記事では数学的な厳密さをいったん脇に置き、働くエンジニアに必要なぶんだけの Big-O を整理します。極限も証明もなしに、「このコードは大きな入力に耐えるか？」を判断する感覚を養うのが目標です。ソートアルゴリズムが異なる計算量でどう違って動くかを目で見たいなら、このサイトのソート可視化ツールを一緒に開いておくと良いでしょう。

O() が実際に意味するもの

Big-O は 入力サイズが大きくなるとき、実行時間（またはメモリ）がどう増えるか を表します。鍵となる言葉は「増える（成長）」です。絶対的な速さではなく、成長の形を語ります。

いくつか重要な性質があります。

定数は捨てる：2n も 100n もどちらも O(n) です。Big-O は入力が大きくなるときの傾向だけを見るので、前に付いた定数倍は無視します。
低い次数は捨てる：n² + n + 5 は O(n²) です。n が非常に大きくなると n² の項が残りを圧倒するので、支配的な項だけ残します。
最悪の場合を基準に：ふつう Big-O は最悪の場合（worst case）を指します。「運が良ければ速い」ではなく「どれだけ悪くてもこの程度」を保証する視点です。

ここで誤解しやすい点があります。Big-O は「このコードが何秒かかる」を語りません。ただ「入力が大きくなるとき、どんな曲線を描いて遅くなるか」だけを語ります。だから二つのアルゴリズムの実際の速さを比べるには Big-O だけでは足りないことがあり、この点は後で改めて触れます。

よく出る計算量クラス

実務で出会う計算量は、実のところ数個に絞られます。それぞれを現実の例とともに見ましょう。

O(1) — 定数時間。 入力サイズと無関係に、常に同じ時間がかかります。配列のインデックスアクセス、ハッシュマップ（辞書）の検索が代表例です。

# 入力がどれだけ大きくても一度のアクセス
value = my_dict[key]      # O(1)
first = my_list[0]        # O(1)

O(log n) — 対数時間。 各ステップごとに問題のサイズが半分ずつ減ります。ソート済み配列での二分探索が典型です。入力が100万個でも約20ステップで終わります。

# ソート済み配列で毎回半分を捨てる -> O(log n)
import bisect
idx = bisect.bisect_left(sorted_list, target)

O(n) — 線形時間。 入力を一度走査します。リストから最大値を探す、条件に合う要素を数えるなど、「すべての要素を一度ずつ見る」たいていの作業です。

# すべての要素をちょうど一度ずつ見る -> O(n)
total = 0
for x in numbers:
    total += x

O(n log n) — 準線形時間。 効率的なソートアルゴリズム（マージソート、クイックソート、Timsort）の計算量です。言語の標準ライブラリの sort() はたいていここに属します。「n 個をソートする」という作業の実質的な下限です。

O(n²) — 二次時間。 すべてのペアを比較する作業です。ネストした二つのループがそれぞれ入力全体を回る形から生じます。小さな入力では平気ですが、大きくなると急激に遅くなります。

# すべてのペアを比較 -> O(n²)
for i in range(len(items)):
    for j in range(len(items)):
        compare(items[i], items[j])

これらのクラスが実際どれだけ違うかを表で見ると腑に落ちます。

n	O(log n)	O(n)	O(n log n)	O(n²)
10	約 3	10	約 33	100
1,000	約 10	1,000	約 10,000	1,000,000
1,000,000	約 20	1,000,000	約 2,000万	1兆

n が100万のとき O(n²) は1兆回の演算です。現代のコンピュータでもかなりかかります。一方 O(n log n) は2,000万回で一瞬です。この表一つが「なぜアルゴリズムの選択が重要か」を凝縮して見せてくれます。

定数が勝つとき — 小さな n とキャッシュ

ここで実務の微妙さが登場します。Big-O は「n が十分に大きいとき」の話です。ところが現実の n はしばしば小さい。そして小さいとき、捨てたはずの定数が再び重要になります。

たとえば O(n²) の挿入ソートと O(n log n) のマージソートを見ましょう。理論上はマージソートが勝つはずですが、n が10〜20のように小さいと挿入ソートのほうが速いことが多いのです。マージソートは再帰呼び出し、配列の分割、マージ用の一時配列の確保といった付帯コスト（定数）が大きいからです。実際、Python や Java の標準ソートは小さな区間では挿入ソートに切り替えます。

キャッシュも定数に大きく影響します。現代の CPU は連続したメモリを読むときはるかに速い（キャッシュ局所性）。だから理論上の計算量が同じか少し悪くても、メモリを連続してアクセスする配列が、ポインタをあちこちたどる連結リストより実際には速いことがよくあります。

  理論上の計算量だけ見ると：
    連結リストの中間挿入 O(1)  vs  配列の中間挿入 O(n)  -> リストの勝ち？

  現実では（キャッシュ局所性のために）：
    小〜中サイズでは配列が連結リストに勝つことが多い
    -> 配列を走査して探すコストより、ポインタ追跡のキャッシュミスのほうが高い

教訓はこうです。Big-O は「大きな絵」を教えてくれますが、実際の性能は定数とハードウェアに左右されます。二つの候補の Big-O が同じか似ているなら、答えは理論ではなく計測にあります。

潜む O(n²) — ネストしたループと N+1 クエリ

O(n²) が怖い理由は、しばしば 見つけにくいから です。明示的な二重 for ループは気づきやすいですが、罠はたいてい隠れています。

一つ目の罠は ループの中に隠れた線形演算 です。

# 一見ループが一つだけなので O(n) に見えるが...
result = []
for item in items:           # n 回反復
    if item in result:       # リストの in 検査は O(n)!
        continue
    result.append(item)
# 実際は O(n²) - 反復のたびに result 全体を走査する

item in result で result はリストなので、in 検査が毎回 O(n) です。これが O(n) のループの中に入り、全体が O(n²) になります。解決策は in 検査を O(1) にすること、すなわち集合（set）を使うことです。

# 集合の in 検査は O(1) -> 全体が O(n)
seen = set()
result = []
for item in items:
    if item in seen:
        continue
    seen.add(item)
    result.append(item)

二つ目の罠は、バックエンド開発で悪名高い N+1 クエリ問題 です。

# 投稿100件を取得（クエリ1回）...
posts = db.query("SELECT * FROM posts LIMIT 100")
for post in posts:
    # 各投稿の著者を個別のクエリで取得 -> 100回のクエリ！
    author = db.query("SELECT * FROM users WHERE id = ?", post.author_id)
    print(author.name)
# 合計 1 + 100 = 101回のクエリ

投稿が増えるほどクエリ数が線形に増え、データが大きくなると応答が急激に遅くなります。各クエリにはネットワークの往復コストが付くので、体感はさらに悪くなります。解決策は、必要なデータを一度のクエリでまとめて取得することです（結合や IN 句、ORM の eager loading）。

# 必要な著者を一度に取得 -> クエリ2回
posts = db.query("SELECT * FROM posts LIMIT 100")
author_ids = [p.author_id for p in posts]
authors = db.query("SELECT * FROM users WHERE id IN (...)", author_ids)
# クエリ合計2回で解決

N+1 はコードだけ見るとふつうのループなので気づきにくいものです。ORM が裏でクエリを代わりに投げてくれるため、いっそう隠れます。クエリログを有効にして「このページを一度開くのにクエリが何回飛ぶか」を確認する習慣が、この罠を防ぎます。

空間計算量も忘れずに

Big-O は時間だけのものではありません。空間計算量 は、アルゴリズムが追加でどれだけメモリを使うかを同じやり方で表します。

# 時間 O(n)、空間 O(1) - 追加メモリは変数いくつかだけ
def sum_list(numbers):
    total = 0
    for x in numbers:
        total += x
    return total

# 時間 O(n)、空間 O(n) - 入力サイズに比例する新しいリストを作る
def double_all(numbers):
    return [x * 2 for x in numbers]

時間と空間はしばしばトレードオフの関係です。先ほど重複除去で集合を使ったのが良い例です。seen 集合に O(n) の追加メモリを使う代わりに、時間計算量を O(n²) から O(n) に下げました。メモリを少し多く使って時間を大きく節約したわけです。

実務では空間計算量は特に大容量データで重要です。ファイルがメモリより大きいと、「すべてリストに読み込む」O(n) 空間の方式はそもそも死にます。こういうときは一行ずつ流して処理するストリーミング（空間 O(1)）に変える必要があります。時間が速くてもメモリが溢れればプログラムは動きません。

償却 — 動的配列の秘密

微妙だが重要な概念が 償却（amortized）計算量 です。「たまに高価な演算があるが、何度かにわたって平均すると安い」という視点です。

Python のリストや他言語の動的配列に要素を追加する append が代表例です。たいていは O(1) ですが、配列が満杯になると、より大きな配列を新たに確保し、既存の要素をすべてコピーする必要があります。このコピーは O(n) です。

  容量4の配列に append し続ける：
  [a][b][c][d]  <- 満杯
  次の append -> 容量8に拡張、4個コピー（この一度だけ O(n)）
  [a][b][c][d][e][_][_][_]
  以降の5回の append はまたそれぞれ O(1)

ところで配列を拡張するとき、ふつうサイズを2倍にします。そのおかげで高価なコピーがだんだん稀にしか起きなくなります。n 個を追加する全体のコストを合計して n で割ると、一度の append あたりの平均コストは O(1) に収束します。これが償却 O(1) です。

肝心なのは、個々の最悪の場合（O(n)）だけを見て怖がらないことです。その高価な演算がどれだけ稀に起きるかを合わせて見てはじめて、実際の性能を正しく理解できます。ハッシュマップの挿入も同じ原理で償却 O(1) です。

いつ最適化をやめるべきか

最後に、おそらく最も重要な実務感覚です。Big-O を学ぶとすべてのコードを最適化したくなりますが、ほとんどのコードは最適化の必要がありません。

ドナルド・クヌースの有名な言葉があります。「早すぎる最適化は諸悪の根源だ（premature optimization is the root of all evil）」。まだボトルネックかどうかも分からないコードを前もって複雑に最適化すると、可読性を損なうだけで利益はありません。

判断基準を整理するとこうです。

n が小さく、今後も小さいなら：O(n²) でも大丈夫です。100個のリストを二重ループで回るのは一瞬です。明確なコードのほうが最適化されたコードより良いのです。
ホットパスか：このコードは毎秒数千回呼ばれる経路か、それとも一日一回回るバッチか？　頻繁に実行される場所から最適化します。
まず計測せよ：推測せず、プロファイラで実際のボトルネックを見つけましょう。開発者の直感はボトルネックの位置をよく外します。時間の90%を食う10%を見つけ、そこだけ手を入れるのが効率的です。
アルゴリズムが先、次に定数：最適化が必要なら、O(n²) を O(n) にするアルゴリズムの改善のほうが、定数を削る微調整よりはるかに大きな効果を出します。

つまり Big-O は「常に最適化せよ」という命令ではなく、「大きくなる危険のある場所を前もって見つける」レーダーです。小さなデータには明確なコードを、大きくなるデータには良い計算量を選ぶバランス感覚が実務の核心です。

おわりに

Big-O は数学の試験ではなく、エンジニアの直感の道具です。「入力が大きくなるとこのコードはどうなるか？」という問いに答えるためのものです。O(1)、O(log n)、O(n)、O(n log n)、O(n²) といういくつかのクラスを体に染み込ませれば、たいていの状況を判断できます。

同時に忘れてはならないのは、Big-O がすべてではないということです。小さな n では定数とキャッシュが勝ち、本当のボトルネックはプロファイラで見つけるべきで、ほとんどのコードは明確さが最適化より重要です。計算量を知ることは、いつ最適化するかを知ることであり、より重要なのは いつ最適化しなくてよいか を知ることです。

ソートアルゴリズムが同じデータでどれだけ違って動くかを目で見たいなら、ソート可視化ツールで O(n²) と O(n log n) の違いを直接感じてみてください。表の数字よりずっと生き生きと迫ってくるはずです。

参考資料

Cormen ほか『Introduction to Algorithms』（関数の成長と漸近記法）
Donald Knuth, "Structured Programming with go to Statements"（早すぎる最適化の引用の出典）
Big-O Cheat Sheet: https://www.bigocheatsheet.com/
"What is the N+1 query problem": https://www.geeksforgeeks.org/what-is-the-n1-query-problem/