快速排序時間複雜度 O(nlogn) 深度解析：logn 到底代表什麼？

快速排序的平均時間複雜度為 O(nlogn)，許多初學者知道 n 代表資料量，但對 logn 的幾何意義感到困惑。本文從分治策略、遞迴樹、數學推導三個維度，徹底講透 logn 的來龍去脈。

核心結論：logn 代表「分治的層數」

快速排序採用分治法：每輪選一個基準，將陣列分為「小於基準」與「大於基準」兩部分，再遞迴處理。理想情況下，每輪都能對半分割，形成一棵平衡二叉樹。log₂n 正是這棵樹的高度（遞迴深度）。

直觀理解：二分查找的類比

就像在有序字典中查字：每次翻到中間頁，根據字序決定往前或往後翻，範圍每次縮減一半。
n 個元素 → 對半分割 → 對半分割 → ... → 剩 1 個
共需 log₂n 次分割。

數學推導

設原始資料量為 N，每次分割為上一輪的一半，經過 x 輪縮減至 1：

N × (1/2)ˣ = 1
→ (1/2)ˣ = 1/N
→ 2ˣ = N
→ x = log₂N

在大 O 符號中，底數常數被忽略，簡記為 logn。

遞迴樹視角

第 0 層：1 個問題，規模 n
第 1 層：2 個問題，規模 n/2
第 2 層：4 個問題，規模 n/4
...
第 k 層：2ᵏ 個問題，規模 n/2ᵏ

當 n/2ᵏ = 1 時，k = log₂n。樹高即為 logn。

每層做多少工作？

每層所有子問題的合併/分區操作總共掃描 n 個元素 → O(n)。
共 logn 層 → 總複雜度 O(n) × O(logn) = O(nlogn)。

最壞情況：O(n²)

若每次基準選最小/最大元素（如已排序陣列且固定選首元素），分割極不平衡：
樹退化為鏈表，高度變 n，總複雜度 O(n²)。
解決：隨機化基準、三數取中法。

總結

• n = 每層處理的元素總數
• logn = 理想分治下的遞迴層數（樹高）
• nlogn = 每層 O(n) × 共 logn 層

下次看到 O(nlogn)，腦海裡浮現的應該是一棵平衡的遞迴二叉樹，而不是抽象的公式。