iPAS AI 應用規劃師中級　科目三　機器學習技術與應用

逐一比對所有客戶相似度，時間複雜度是多少？

原題 33

某資料科學團隊正在開發一個客戶相似度比對系統，用於計算所有客戶之間的相似度分數。若系統需逐一比對每一位客戶與其他所有客戶的資料組合，此時演算法的時間複雜度最可能為哪一種？其代表意義為何？

白話

一個系統要計算所有客戶彼此之間的相似度，做法是讓每位客戶都和其他每位客戶比對一次。

問你：這種「每個人和其他所有人都比一遍」的演算法，時間複雜度是哪一種？

點選你的答案。

← 回 50 題列表回 iPAS 備考總覽

01　總結

一句話總結

每位客戶都要和其他所有客戶比對一次，答案是 O(n²)：客戶數量增加 10 倍，比對次數增加 100 倍，執行時間與資料量的平方成正比，資料量一大就會非常慢。

02　情境

先感受問題：客戶從 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²) 的意思：執行時間和客戶數量的「平方」成正比。

當公司客戶從幾千人成長到幾十萬人，這個系統會變得慢到無法使用。

03　對照

為什麼其他複雜度描述不適合這個問題？

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²) 的系統很快就會慢到無法接受，這是工程師選擇演算法時必須考慮的首要因素之一。

04　解法

計算比對次數：兩層迴圈就是 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²) — 執行時間與資料量平方成正比。

技術版：大 O 表示法的規則與常見複雜度比較

中級考試大概率會考程式碼跟公式，所以這部分你還是要學。但如果現在學起來很痛苦，可以先跳過，等讀完其他題目回頭再來。

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²)？

05　陷阱

為什麼其他選項是錯的

選項 A　O(n)：線性成長

字面在說什麼：客戶相似度比對系統的執行時間和客戶數量成線性關係。

為什麼不對：O(n) 的演算法代表每增加一個客戶，只多一份固定工作量。但在相似度比對中，每增加一個客戶，他要和現有所有客戶都比一次，工作量增加了「n 份」，不是「1 份」。只掃過每個客戶一次才是 O(n)，而非兩兩配對。

誰會選錯：直覺上覺得「n 個客戶就做 n 次事情」的人，沒有意識到「兩兩配對」的組合特性讓工作量是 n²，不是 n。

選項 C　O(1)：固定時間

字面在說什麼：客戶相似度比對的執行時間不隨客戶數量改變。

為什麼不對：O(1) 表示執行時間完全不受輸入規模影響，例如雜湊表查找一個特定元素。相似度比對顯然需要做更多工作當客戶增加，O(1) 完全不合邏輯。

誰會選錯：記憶考試時猜測的人，沒有真正理解各複雜度的意義。通常只有「在 O 表示法中數字最小的那個感覺最快」的錯誤直覺。

選項 D　O(log n)：對數成長

字面在說什麼：客戶相似度比對的執行時間呈對數成長，每次操作把問題縮小一半。

為什麼不對：O(log n) 通常對應「分而治之」的演算法，如二分搜尋：每次操作都把搜尋範圍縮小一半。相似度比對不具有「每次縮小問題」的結構，而是要遍歷所有配對組合。O(log n) 的演算法不需要看所有元素，相似度比對必須看所有配對。

誰會選錯：知道 O(log n) 是「很好的複雜度」，錯誤地以為系統可以做得這麼有效率，沒有理解這種系統本質上需要窮舉所有配對。

06　變形

同個考點下次怎麼變形

變形 1　邊界

直覺：如果已知相似度是對稱的（A 和 B 的相似度 = B 和 A 的相似度），可以減少比對次數嗎？複雜度會變嗎？

答案：可以減少約一半的計算：只計算 i < j 的配對，共 n×(n-1)/2 次。但大 O 複雜度仍然是 O(n²)，因為省略常數 1/2 後還是 O(n²)。大 O 描述成長速率，不是精確計算量。

變形 2　反例

直覺：KNN（K 近鄰）演算法在預測一個新樣本時是 O(n²) 嗎？

答案：標準 KNN 預測一個樣本時需要計算它和訓練集所有 n 個樣本的距離，這是 O(n) 而非 O(n²)。但如果要預測 n 個新樣本，就是 O(n²)。當問「計算訓練集所有點之間的距離矩陣」時，才是 O(n²)，要分清楚「計算一個 vs 計算所有」。

變形 3　升級版

直覺：有沒有方法讓相似度比對不是 O(n²)？用什麼技術？

答案：有幾種近似方法：LSH（局部敏感雜湊）可以在 O(n) 或 O(n log n) 內找出近似近鄰，犧牲一些精確度換取效率；向量資料庫（如 Faiss、Pinecone）用近似最近鄰搜尋，對高維向量特別有效；HNSW 演算法可以達到接近 O(log n) 的查詢速度。這些都是大規模相似度系統的實際解法。

變形 4　跨領域

直覺：協同過濾（Collaborative Filtering）推薦系統計算使用者相似度矩陣，也是 O(n²) 嗎？

答案：是的，基於記憶的協同過濾（Memory-based CF）需要計算所有使用者配對的相似度矩陣，時間複雜度是 O(n²)，這也是大型推薦系統不直接用這種方法的原因。矩陣分解（Matrix Factorization）等基於模型的方法可以降低複雜度，這也是 Netflix Prize 之後主流推薦系統的方向。

變形 5　評估指標

直覺：在評估一個演算法的效率時，除了時間複雜度，還有什麼重要的複雜度概念？

答案：空間複雜度（Space Complexity）：演算法需要多少記憶體。n 個客戶的相似度矩陣需要 O(n²) 空間，10 萬客戶的相似度矩陣大小約 10¹⁰ 個數值，儲存就很困難。此外還有最壞情況（Worst Case）vs 平均情況（Average Case）vs 最好情況（Best Case）複雜度之分，大 O 通常指最壞情況。

07　延伸

想再往下看，這 5 個

K 近鄰（KNN）最典型的需要計算樣本間距離的演算法，理解 KNN 能直觀感受 O(n²) 相似度計算的代價。
餘弦相似度（Cosine Similarity）計算兩個向量之間相似度的常用方法，也是客戶相似度比對系統中常用的距離函數。
演算法（Algorithm）時間複雜度分析的基礎概念，大 O 表示法描述演算法在最壞情況下的執行時間成長率。
矩陣分解（Matrix Factorization）推薦系統中繞開 O(n²) 問題的主要方法，將相似度矩陣分解成低維表示，效率更高。
降維處理（Dimensionality Reduction）高維向量相似度計算成本高，降維能在保留主要資訊的前提下讓相似度計算更快速。