小編精選 - 技術文章翻譯 · 06月24日

用 Rails 學習計算複雜度（Big-O）入門～把「大致上快／慢」說成具體語言～

計算量（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) … 從第一個人開始，一個一個問「是你嗎？」。最壞要問 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)）

兩個列表做比對的處理。照直覺寫，很容易變成雙重迴圈，也就是 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]             # 用 key 一次取出 🙆
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²)」，所以這點還是很值得自己留意！

原文出處：https://qiita.com/akachiryo/items/90db7bf21b6546fce911