計算量（Big-O）入門 〜「なんとなく速い／遅い」を言葉にする〜
お疲れ様です！
前回はメモリ管理の話を書きましたが、今回はその続きで 計算量（Big-O記法） についてまとめてみました 
「このコード、データが増えたら大丈夫？」をパッと判断するための話です。
興味ある方は読んでいただけると嬉しいです 
そもそも計算量とは？
ひとことで言うと 「データが増えたとき、処理時間やメモリがどれくらいの勢いで増えるか」 を表したものです。
大事なのは 「速い／遅い」ではなく「増え方（伸び率）」 を見ているという点です。
データが10倍になったとき…
- 変わらない（10件でも100万件でも一瞬）
- 10倍になる
- 100倍になる
この「増え方」を、O(1)・O(n)・O(n²) のように表すのが Big-O記法 です。
出典：Big-O Cheat Sheet（Eric Rowell）
横軸が「データ量（elements）」、縦軸が「処理回数（operations）」です。右上に行くほど"データが増えたときに急激に重くなる"＝ヤバい、というのが色で一目でわかります。
n は「データの件数」を表します。O(n) は「件数に比例して増える」という意味です。
よく出るBig-O 早見表
上から速い順です。
| 記法 | 呼び方 | データが10倍になると | 身近な例 |
|---|---|---|---|
| O(1) | 定数 |
変わらない 
|
配列の n 番目を取り出す |
| O(log n) | 対数 | ほぼ変わらない | 辞書を半分ずつ絞って引く（二分探索） |
| O(n) | 線形 | 10倍 | リストを先頭から全部見る |
| O(n log n) | 準線形 | 十数倍 | 高速なソート |
| O(n²) | 二乗 |
100倍
|
二重ループで総当たり |
O(n²) は要注意。10件なら100回で済みますが、1万件だと1億回になります。
「ループの中でループ」を見たら、気をつけましょう。
イメージで掴む
「100人の中から特定の1人を探す」例で考えてみます。
- O(n) … 先頭から1人ずつ「あなた？」と聞いていく。最悪100回 → 人数に比例
- O(log n) … 名簿が並んでいるなら、真ん中を見て「前半／後半」を半分ずつ絞る。100人でも約7回で見つかる
-
O(1) … 「3番目の人」と最初から分かっている。一発
実例①：Array#include? を Set に変える（O(n) → O(1)）
Rubyでよくある改善です。ループの中で「含まれてる？」を繰り返すと、Arrayは毎回 O(n) で全体が重くなります。
# ❌ ダメな例：include? が毎回 O(n)。全体で O(n × m) になる
ng_words = ["spam", "ng", ...] # 1万件
comments.each do |c|
next if ng_words.include?(c.body) # 毎回1万件を先頭から線形探索💥
end
# ⭕ 良い例：Set にすると include? が O(1)。全体が O(m) で済む
require "set"
ng_words = Set.new(["spam", "ng", ...]) # 中身は Hash なので一発で判定できる
comments.each do |c|
next if ng_words.include?(c.body) # O(1) 🙆
end
Set は「重複なし・順序なしの集合」。内部が Hash でできているため、include?（含まれるか判定）が O(1) になります。
「順番が大事」「重複を持ちたい」なら Array のままが正解です。
実例②：二重ループを Hash 化する（O(n²) → O(n)）
2つのリストを突き合わせる処理。素直に書くと二重ループ＝ O(n²) になりがちです。
# ❌ ダメな例：users × orders の総当たり → O(n²)
users.each do |u|
orders.each do |o|
matched = o if o.user_id == u.id # 内側で毎回ぐるぐる💥
end
end
# ⭕ 良い例：先に Hash 化しておけば O(1) で引ける → 全体 O(n)
orders_by_user = orders.group_by(&:user_id) # 一度だけ Hash 化
users.each do |u|
matched = orders_by_user[u.id] # キーで一発 🙆
end
「内側のループ」を「Hashでの一発引き」に置き換えるのが定番テクニックです。
時間だけじゃない：空間計算量（メモリ）
Big-O は 時間だけでなく メモリ（空間計算量） にも使います。
ここで前回のメモリの記事と繋がります。
-
User.all… 全件をメモリに載せる → 空間 O(n) -
User.find_each(batch_size: 1000)… 一定件数ずつ → 空間 O(1)（に近い）
実例②の Hash 化は、時間を O(n²)→O(n) に改善する代わりに、Hashの分メモリを使います（空間 O(n)）。
このように「時間を速くするとメモリが増える」など、時間と空間はトレードオフになることがよくあります。
最後に
- Big-O は 「データが増えたときに破綻しないか」を見るための共通言語です。完璧に暗記する必要はなく、「ループの中でループ（O(n²)）になってない？」「
include?を繰り返してない？」に気づけるだけで十分役立ちます - 速さ・メモリ・可読性は トレードオフ。件数が少ないうちは素直なコードで十分ですが、大量データで効いてくる話だという感覚も大事です
- AI は動くコードは出してくれますが、「それ、1万件で O(n²) になりますよ」までは指摘してくれないことがありますのでぜひ意識してみてください！