逐一比對所有客戶相似度，時間複雜度是多少？
原題
某資料科學團隊正在開發一個客戶相似度比對系統，用於計算所有客戶之間的相似度分數。若系統需逐一比對每一位客戶與其他所有客戶的資料組合，此時演算法的時間複雜度最可能為哪一種？其代表意義為何？
白話
一個系統要計算所有客戶彼此之間的相似度，做法是讓每位客戶都和其他每位客戶比對一次。
問你：這種「每個人和其他所有人都比一遍」的演算法，時間複雜度是哪一種？
先自己選一個答案，再看完整解析。
一句話總結
每位客戶都要和其他所有客戶比對一次，答案是 O(n²)：客戶數量增加 10 倍，比對次數增加 100 倍，執行時間與資料量的平方成正比，資料量一大就會非常慢。
情境
先感受問題：客戶從 100 人變 1000 人，比對次數爆炸
「精準行銷科技」的工程師王志明要建立一個「找出相似客戶」的系統，讓業務員看到「和這個客戶最像的前 10 名客戶」。
他的第一個版本：每個客戶都和其他所有客戶逐一計算相似度分數。
100 個客戶：每人比 99 次，共 100 × 99 ÷ 2 ≈ 4,950 次比對
1,000 個客戶：每人比 999 次，共約 499,500 次比對
10,000 個客戶：共約 50,000,000 次比對
100,000 個客戶：共約 5,000,000,000 次比對（50 億次！）
客戶數量翻 10 倍，比對次數卻翻了約 100 倍。這就是時間複雜度 O(n²) 的意思：執行時間和客戶數量的「平方」成正比。
當公司客戶從幾千人成長到幾十萬人，這個系統會變得慢到無法使用。
舊方法
為什麼其他複雜度描述不適合這個問題？
- O(1) 是固定時間：不管資料量多少，執行時間都一樣，例如「讀取陣列第一個元素」。客戶相似度比對的工作量顯然隨客戶數增加，絕對不可能是 O(1)。
- O(n) 是線性成長：每多一個客戶，工作量就多一份，例如「掃過所有客戶一次找最大值」。但我們的系統每新增一個客戶，他要和所有現有客戶都比一次，工作量增加不只一份，所以不是 O(n)。
- O(log n) 是對數成長：每次操作把問題縮小一半，例如「在排好序的清單裡用二分搜尋找某人」。兩個人的相似度比對不是「縮小問題」的結構，所以不是 O(log n)。
- O(n²) 才是雙層迴圈的複雜度：第一層迴圈跑 n 次（每個客戶），第二層迴圈也跑 n 次（和其他每個客戶比），合計 n × n = n² 次操作。
- O(n²) 在實際系統中的代價：資料量一增加，O(n²) 的系統很快就會慢到無法接受，這是工程師選擇演算法時必須考慮的首要因素之一。
新方法
計算比對次數：兩層迴圈就是 n²
王志明的相似度比對系統用雙層迴圈實作：
第一層迴圈：遍歷每一個客戶 i（共 n 次）
第二層迴圈：對每個 i，遍歷每一個客戶 j（共 n 次）
如果 i ≠ j，計算 i 和 j 的相似度
總執行次數：n × n = n²（精確說是 n×(n-1)，大 O 省略常數和低階項）
時間複雜度 O(n²) 的直覺理解：把所有客戶排成一張表格，行是「客戶 i」，列是「客戶 j」，需要填滿整張 n×n 的表（排除對角線）。表格大小和 n 的平方成正比。
這就是選項 B 講的：O(n²)，執行時間與資料量平方成正比。
中級考試大概率會考程式碼跟公式，所以這部分你還是要學。但如果現在學起來很痛苦，可以先跳過，等讀完其他題目回頭再來。
Step 1 純故事版
想像你要讓一個班級裡的所有同學互相握手：10 人，每人握 9 次，共 45 次握手。100 人，共 4950 次。1000 人，共約 50 萬次。人數變 10 倍，握手次數變 100 倍。這就是 O(n²) 的直覺：每加一個人，他要和所有人都握一次手，所以工作量不是「多一份」而是「多了 n 份」。
Step 2 常見複雜度對照表
| 複雜度 | 名稱 | n=100 時的運算量 | 典型場景 |
|---|---|---|---|
| O(1) | 常數時間 | 1 | 讀陣列第一個元素 |
| O(log n) | 對數時間 | 約 7 | 二分搜尋 |
| O(n) | 線性時間 | 100 | 掃描整個清單 |
| O(n log n) | 線性對數 | 約 700 | 快速排序（平均） |
| O(n²) | 平方時間 | 10,000 | 雙層迴圈比對 |
| O(2ⁿ) | 指數時間 | 約 10³⁰ | 暴力列舉所有子集 |
Step 3 符號角色表
- O（大 O）：Big-O 表示法，描述演算法最壞情況下的成長速率
- n：輸入規模，本題中是客戶數量
- O(n²)：當 n 增大時，執行時間以 n 的平方速度增加，常見於雙層迴圈
- 省略常數：O(2n²) 和 O(n²) 都寫成 O(n²)，大 O 只關注成長速率的數量級
Step 4 公式推導
n 個客戶，兩兩比對的精確次數： C(n, 2) = n × (n−1) / 2 n = 100：100 × 99 / 2 = 4,950 n = 1,000：1,000 × 999 / 2 = 499,500 n = 10,000：10,000 × 9,999 / 2 ≈ 50,000,000 大 O 分析： n × (n−1) / 2 = (n² − n) / 2 ≈ n² / 2 （當 n 很大時，−n 可忽略） = O(n²) （省略常數 1/2）
Step 5 自我複述
- 為什麼大 O 表示法會省略常數（如 1/2 或 2）？這樣做的意義是什麼？
- 雙層迴圈一定是 O(n²) 嗎？舉一個例外的情況。
- O(n²) 的演算法當 n = 1,000,000 時大概需要幾次操作？對工程系統有什麼影響？
- KNN（K 近鄰）計算時也是 O(n²) 嗎？有沒有方法加速？
- 除了相似度計算，還有哪些 ML 演算法是 O(n²)？
錯選項
為什麼其他選項是錯的
AO(n)：線性成長
字面在說什麼
客戶相似度比對系統的執行時間和客戶數量成線性關係。
為什麼不對
O(n) 的演算法代表每增加一個客戶，只多一份固定工作量。但在相似度比對中，每增加一個客戶，他要和現有所有客戶都比一次，工作量增加了「n 份」，不是「1 份」。只掃過每個客戶一次才是 O(n)，而非兩兩配對。
誰會選錯
直覺上覺得「n 個客戶就做 n 次事情」的人，沒有意識到「兩兩配對」的組合特性讓工作量是 n²，不是 n。
CO(1)：固定時間
字面在說什麼
客戶相似度比對的執行時間不隨客戶數量改變。
為什麼不對
O(1) 表示執行時間完全不受輸入規模影響，例如雜湊表查找一個特定元素。相似度比對顯然需要做更多工作當客戶增加，O(1) 完全不合邏輯。
誰會選錯
記憶考試時猜測的人，沒有真正理解各複雜度的意義。通常只有「在 O 表示法中數字最小的那個感覺最快」的錯誤直覺。
DO(log n)：對數成長
字面在說什麼
客戶相似度比對的執行時間呈對數成長，每次操作把問題縮小一半。
為什麼不對
O(log n) 通常對應「分而治之」的演算法，如二分搜尋：每次操作都把搜尋範圍縮小一半。相似度比對不具有「每次縮小問題」的結構，而是要遍歷所有配對組合。O(log n) 的演算法不需要看所有元素，相似度比對必須看所有配對。
誰會選錯
知道 O(log n) 是「很好的複雜度」，錯誤地以為系統可以做得這麼有效率，沒有理解這種系統本質上需要窮舉所有配對。
變形題
同個考點下次怎麼變形
答案
可以減少約一半的計算：只計算 i < j 的配對，共 n×(n-1)/2 次。但大 O 複雜度仍然是 O(n²)，因為省略常數 1/2 後還是 O(n²)。大 O 描述成長速率，不是精確計算量。
答案
標準 KNN 預測一個樣本時需要計算它和訓練集所有 n 個樣本的距離，這是 O(n) 而非 O(n²)。但如果要預測 n 個新樣本，就是 O(n²)。當問「計算訓練集所有點之間的距離矩陣」時，才是 O(n²)，要分清楚「計算一個 vs 計算所有」。
答案
有幾種近似方法：LSH（局部敏感雜湊）可以在 O(n) 或 O(n log n) 內找出近似近鄰，犧牲一些精確度換取效率；向量資料庫（如 Faiss、Pinecone）用近似最近鄰搜尋，對高維向量特別有效；HNSW 演算法可以達到接近 O(log n) 的查詢速度。這些都是大規模相似度系統的實際解法。
答案
是的，基於記憶的協同過濾（Memory-based CF）需要計算所有使用者配對的相似度矩陣，時間複雜度是 O(n²)，這也是大型推薦系統不直接用這種方法的原因。矩陣分解（Matrix Factorization）等基於模型的方法可以降低複雜度，這也是 Netflix Prize 之後主流推薦系統的方向。
答案
空間複雜度（Space Complexity）：演算法需要多少記憶體。n 個客戶的相似度矩陣需要 O(n²) 空間，10 萬客戶的相似度矩陣大小約 10¹⁰ 個數值，儲存就很困難。此外還有最壞情況（Worst Case）vs 平均情況（Average Case）vs 最好情況（Best Case）複雜度之分，大 O 通常指最壞情況。
延伸
想再往下看，這 5 個
- K 近鄰（KNN）
最典型的需要計算樣本間距離的演算法，理解 KNN 能直觀感受 O(n²) 相似度計算的代價。 - 餘弦相似度（Cosine Similarity）
計算兩個向量之間相似度的常用方法，也是客戶相似度比對系統中常用的距離函數。 - 演算法（Algorithm）
時間複雜度分析的基礎概念，大 O 表示法描述演算法在最壞情況下的執行時間成長率。 - 矩陣分解（Matrix Factorization）
推薦系統中繞開 O(n²) 問題的主要方法，將相似度矩陣分解成低維表示，效率更高。 - 降維處理（Dimensionality Reduction）
高維向量相似度計算成本高，降維能在保留主要資訊的前提下讓相似度計算更快速。