当前位置：首页 > news >正文

LeetCode 复杂度论证：主定理的推导与算法分析实战

news 2026/6/30 1:01:02

LeetCode 复杂度论证：主定理的推导与算法分析实战

一、复杂度分析不是猜的——从"感觉是 O(n log n)"说起

刷题时经常看到这样的题解："外层循环 log n 次，内层循环 n 次，所以总复杂度 O(n log n)"。这个结论碰巧是对的，但推导过程经不起推敲。如果内层循环的规模不是固定的 n，而是每层递减呢？比如归并排序的合并操作，每层的总工作量确实是 n，但为什么？

主定理（Master Theorem）是解决分治算法复杂度论证的通用工具。它给出了递推关系 T(n) = aT(n/b) + f(n) 的精确渐近界。理解主定理不仅能让你在面试中给出严谨的复杂度证明，还能帮你识别那些"直觉上对但逻辑上有漏洞"的分析。

本文将从主定理的推导出发，结合 LeetCode 高频分治题目，给出完整的复杂度论证实战。

二、主定理的数学推导与三种情形

2.1 递推关系与递归树

分治算法的递推关系一般形式为：

T(n) = a * T(n/b) + f(n)

其中：

a：子问题个数（递归分支数）
n/b：每个子问题的规模
f(n)：分解和合并的代价

理解这个递推式的最佳方式是画递归树。每层有 a^i 个节点，每个节点规模为 n/b^i，第 i 层的总工作量为 a^i * f(n/b^i)。

graph TD A["第0层：f(n)"] --> B1["第1层节点1：f(n/b)"] A --> B2["第1层节点2：f(n/b)"] A --> B3["第1层节点a：f(n/b)"] B1 --> C1["第2层：a^2 个节点<br/>每个 f(n/b^2)"] B2 --> C2["第2层：a^2 个节点<br/>每个 f(n/b^2)"] B3 --> C3["..."] C1 --> D["叶子层：a^(log_b n) 个节点<br/>每个 T(1)"]

2.2 主定理的三种情形

主定理的核心是比较 f(n) 和 n^(log_b a) 的增长速度：

情形	条件	结论
Case 1	f(n) = O(n^(log_b a - ε))，ε > 0	T(n) = Θ(n^(log_b a))
Case 2	f(n) = Θ(n^(log_b a) * log^k n)，k >= 0	T(n) = Θ(n^(log_b a) * log^(k+1) n)
Case 3	f(n) = Ω(n^(log_b a + ε))，ε > 0	T(n) = Θ(f(n))

直观理解：

Case 1：叶子节点的工作量占主导，合并代价可忽略
Case 2：叶子节点和合并代价同阶，需要乘以 log 因子
Case 3：合并代价占主导，递归分解的开销可忽略

2.3 经典算法的主定理分析

flowchart LR A[归并排序<br/>a=2, b=2, f(n)=O(n)] --> B["n^(log_2 2) = n<br/>f(n) = Θ(n^1 * log^0 n)<br/>Case 2, k=0"] B --> C["T(n) = Θ(n log n)"] D[二分查找<br/>a=1, b=2, f(n)=O(1)] --> E["n^(log_2 1) = 1<br/>f(n) = O(n^0 * log^0 n)<br/>Case 2, k=0"] E --> F["T(n) = Θ(log n)"] G[快速排序最优<br/>a=2, b=2, f(n)=O(n)] --> H["同归并排序<br/>T(n) = Θ(n log n)"]

三、LeetCode 分治题的复杂度论证实战

3.1 归并排序的应用——逆序对计数（LeetCode 剑指 Offer 51）

def reverse_pairs(nums: list[int]) -> int: """ 计算数组中的逆序对数量。 基于归并排序的修改版，在合并阶段统计逆序对。 时间复杂度：T(n) = 2T(n/2) + O(n) 由主定理 Case 2，T(n) = Θ(n log n) 空间复杂度：O(n)，临时数组开销 """ if len(nums) <= 1: return 0 temp = [0] * len(nums) def merge_sort_count(left: int, right: int) -> int: """对 [left, right) 区间排序并统计逆序对。""" if right - left <= 1: return 0 mid = (left + right) // 2 # 递归处理左右两半 count = merge_sort_count(left, mid) + merge_sort_count(mid, right) # 合并阶段统计跨区间的逆序对 i, j, k = left, mid, left while i < mid and j < right: if nums[i] <= nums[j]: temp[k] = nums[i] i += 1 else: # nums[i] > nums[j]，左边 [i, mid) 都与 nums[j] 构成逆序对 temp[k] = nums[j] count += mid - i j += 1 k += 1 # 处理剩余元素 while i < mid: temp[k] = nums[i] i += 1 k += 1 while j < right: temp[k] = nums[j] j += 1 k += 1 # 将排序结果写回原数组 nums[left:right] = temp[left:right] return count return merge_sort_count(0, len(nums))

复杂度论证：

递推关系：T(n) = 2T(n/2) + O(n)
a = 2, b = 2, f(n) = O(n)
n^(log_2 2) = n^1 = n
f(n) = Θ(n^1 * log^0 n)，属于 Case 2（k = 0）
因此 T(n) = Θ(n log n)

3.2 快速选择算法——第 K 大元素（LeetCode 215）

import random def find_kth_largest(nums: list[int], k: int) -> int: """ 快速选择算法找第 k 大元素。 平均时间复杂度：T(n) = T(n/2) + O(n) 由主定理 Case 1（a=1, b=2），T(n) = Θ(n) 最坏时间复杂度：T(n) = T(n-1) + O(n) = O(n^2) 空间复杂度：O(1) 原地分区 """ target = len(nums) - k # 转换为第 target 小 def partition(left: int, right: int) -> int: """Lomuto 分区方案，随机选择 pivot 避免最坏情况。""" # 随机化 pivot 选择，降低最坏情况概率 pivot_idx = random.randint(left, right) nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx] pivot = nums[right] store = left for i in range(left, right): if nums[i] < pivot: nums[store], nums[i] = nums[i], nums[store] store += 1 nums[store], nums[right] = nums[right], nums[store] return store def quick_select(left: int, right: int) -> int: """递归选择，只进入目标所在的一侧。""" if left == right: return nums[left] pivot_pos = partition(left, right) if pivot_pos == target: return nums[pivot_pos] elif pivot_pos < target: return quick_select(pivot_pos + 1, right) else: return quick_select(left, pivot_pos - 1) return quick_select(0, len(nums) - 1)

复杂度论证：