如何推导QuickSort平均时间复杂度？求解其递推关系式

首先明确平均情况的递推式：

T(n) = Σₚ=1ⁿ(1/n (T(p-1)+T(n-p)))+n-1

步骤1：简化求和项 #

观察求和中的两个部分：Σₚ=1ⁿ T(p-1) 和 Σₚ=1ⁿ T(n-p)

• 对Σₚ=1ⁿ T(p-1)，令k=p-1，当p=1时k=0，p=n时k=n-1，求和等价于Σₖ=0ⁿ⁻¹ T(k)
• 对Σₚ=1ⁿ T(n-p)，令k=n-p，当p=1时k=n-1，p=n时k=0，求和顺序反转不影响结果，同样等价于Σₖ=0ⁿ⁻¹ T(k)

结合T(0)=0（空数组排序时间为0），原递推式简化为：
T(n) = (2/n) * Σₖ=1ⁿ⁻¹ T(k) + n - 1

步骤2：构造差分递推式 #

将式子两边乘n，得到：
n*T(n) = 2*Σₖ=1ⁿ⁻¹ T(k) + n(n-1)

再写出n-1时的表达式（n≥2）：
(n-1)*T(n-1) = 2*Σₖ=1ⁿ⁻² T(k) + (n-1)(n-2)

用第一个式子减去第二个式子，左边为n*T(n) - (n-1)*T(n-1)，右边求和项相减后剩余2*T(n-1)，多项式部分化简为：
n(n-1) - (n-1)(n-2) = 2(n-1)

整理后得到：
n*T(n) = (n+1)*T(n-1) + 2(n-1)

步骤3：转化为可求和的形式 #

两边同时除以n(n+1)，定义S(n) = T(n)/(n+1)，递推式变为：
S(n) = S(n-1) + 2(n-1)/(n(n+1))

对分式做部分分式分解：
(n-1)/(n(n+1)) = -1/n + 2/(n+1)
因此：
2(n-1)/(n(n+1)) = -2/n + 4/(n+1)

步骤4：展开求和求解 #

初始条件：n=1时T(1)=0，所以S(1)=0/(1+1)=0

展开S(n)：
S(n) = Σₖ=2ⁿ [ -2/k + 4/(k+1) ]

拆分求和项并调整下标：

• Σₖ=2ⁿ (-2/k) = -2*(Hₙ - 1)，其中Hₙ是第n个调和数
• Σₖ=2ⁿ 4/(k+1) = 4*(Hₙ₊₁ - 1 - 1/2) = 4*(Hₙ₊₁ - 3/2)

合并计算后：
S(n) = 2Hₙ + 4/(n+1) - 4

代回T(n) = (n+1)*S(n)，化简得：
T(n) = 2(n+1)Hₙ - 4n

步骤5：渐进复杂度近似 #

调和数的近似公式为Hₙ ≈ ln(n) + γ（γ≈0.5772为欧拉-马歇罗尼常数），代入后忽略低阶项：
T(n) ≈ 2n ln(n) + 2γ n - 4n

若以2为底的对数计算（算法分析常用底数），ln(n) = log₂(n)/log₂(e)，则2ln(n) ≈ 1.386log₂(n)，最终得到：
T(n) ≈ 1.38n log₂(n) + O(n)

补充说明 #

主定理不适用于该递推式，因为主定理针对的是T(n)=aT(n/b)+f(n)形式的分治递推，而本题递推为求和形式，需通过差分、调和数展开的方法求解。

内容的提问来源于stack exchange，提问作者Vincenzo Narendra