快速排序的平均时间复杂度O(n log n)的期望分析

快速排序的平均时间复杂度 O(n log n) 并非偶然，而是算法设计与概率分析共同作用的结果。本指南将手把手拆解这一期望分析的核心步骤，揭示其高效的根本原因。

1. 理解快速排序的核心机制

快速排序的核心是 分治法，其性能完全取决于 划分 步骤的效果。

1. 选择一个元素作为“基准”（Pivot）。可以简单选取数组的第一个、最后一个或中间的元素。
2. 执行划分：重排 数组，使得所有小于基准的元素都移到其左侧，所有大于基准的元素都移到其右侧。此时，基准处于其最终的正确位置。
3. 递归排序：分别对 基准左侧的子数组和右侧的子数组，重复 步骤 1 和 2，直到子数组的长度为 0 或 1。

总时间消耗主要取决于递归树的深度和每一层划分的工作量。

2. 分析时间复杂度的关键因素

平均时间复杂度 O(n log n) 的得出，依赖于两个核心观察。

1. 递归树的深度期望是 log n 级别。

   • 想象递归过程形成一棵树，每次划分产生两个子问题。
   • 在最坏情况（如数组已有序）下，每次划分都极不均衡，树深度达到 n，导致 O(n^2) 时间。
   • 但在平均情况下，基准的选择是“随机”的（或等效于随机）。一个“好”的基准能将数组大致等分为两部分。
   • 概率分析表明，平均而言，递归树的高度是 O(log n)。这意味着需要递归 log n 次才能将问题分解到最小子问题。

2. 每一层递归的总工作量是 O(n)。

   • 在递归树的任意一层，所有子问题的划分工作之和，恰好是遍历当前层所有元素的总和。
   • 例如，在顶层，划分整个数组的工作量是 n。在下一层，假设数组被大致均分，则划分两个子数组的工作量之和约为 n/2 + n/2 = n。
   • 以此类推，每一层递归的总工作量都近似为 n。

3. 推导 O(n log n) 的数学期望

结合以上两点，我们可以用公式描述总工作量 T(n) 的期望。

1. 定义递归关系。

   • 设 T(n) 为对 n 个元素的数组进行快速排序的期望比较次数。
   • 基准的选择是随机的，设它将数组划分为大小为 i 和 n-i-1 的两个部分，其中 i 是一个随机变量（0 <= i <= n-1）。
   • 则划分过程本身需要 n-1 次比较（每个元素与基准比较一次）。递归排序两个子问题的期望代价是 T(i) 和 T(n-i-1)。
   • 由于划分是随机的，i 取 0 到 n-1 中每一个值的概率都是 1/n。因此，T(n) 的递归关系为：
     $$ T(n) = (n-1) + \frac{1}{n} \sum_{i=0}^{n-1} [T(i) + T(n-i-1)] $$

2. 简化递推公式。

   • 由于 T(i) 和 T(n-i-1) 在求和中的对称性，可以简化。
   • 定义 T(0) = 0 和 T(1) = 0（不需要比较）。
   • 将上式两边乘以 n，进行一系列数学变换（涉及求和性质），可以推导出一个更易处理的递推式：
     $$ n T(n) = n(n-1) + 2 \sum_{k=1}^{n-1} T(k) $$
   • 这个变换是推导的关键一步，它将双和转化为单和。

3. 证明 T(n) = O(n log n)。

   • 猜想：我们猜测 T(n) <= c n log n 对于某个常数 c 成立（这里 log 默认以 2 为底）。
   • 归纳基础：对于小的 n（如 n=2），T(2) = 1，而 c*2*log2 = 2c。只要 c >= 1/2，不等式成立。
   • 归纳步骤：假设对于所有 k < n，T(k) <= c k log k 成立。将其代入变换后的递推式：
     $$ \begin{aligned} n T(n) &= n(n-1) + 2 \sum_{k=1}^{n-1} T(k) \\ &\le n(n-1) + 2 \sum_{k=1}^{n-1} c k \log k \\ &\le n^2 + 2c \int_{1}^{n} x \log x \, dx \quad (\text{用积分近似求和}) \end{aligned} $$
   • 计算积分 ∫ x log x dx，并代入上下限，经过代数运算后，最终可以证明存在常数 c，使得 T(n) <= c n log n 成立。
   • 因此，快速排序的期望时间复杂度为 O(n log n)。

这个期望分析证明了，在基准随机选择（或输入随机）的前提下，快速排序平均只需要 O(n log n) 次操作，这是它成为最常用排序算法之一的理论基石。