【算法笔记】差消法化简高阶递推方程示例：计算快速排序平均时间复杂

作者: w8ed | 来源:发表于2019-03-25 23:02 被阅读0次

快速排序代码如下：

void quickSort(int a*, int p, int r)
{
    if(p < r)
    {
        int q = partition(a, p, r); //划分
        quickSort(a, p, q-1);
        quickSort(a, q+1, r);
    }
}

每一趟的工作量 = 子问题的工作量 + 划分的工作量（即划分的比较次数）
下图展示了n种可能的输入：

每一次划分的比较次数为 n-1，则工作量总和有：

上述工作量总和可简写为
$2\sum\limits_{i=1}^{n-1}T(i)+n(n-1)$

假设首元素排好序在每个位置是等概率的，则有:

$\begin{aligned} &T(n) = \frac{2}{n}\sum\limits_{i=1}^{n-1}T(i)+O(n), n>1\\ &T(1)=0\\ \end{aligned}$

下面利用差消法化简上述递推方程，即
$T(n) = \frac{2}{n}\sum\limits_{i=1}^{n-1}T(i)+cn$
首先，两边同时乘n，有
$nT(n) = 2\sum\limits_{i=1}^{n-1}T(i)+cn^2 \tag1$
将 $n-1$ 带入，得：
$(n-1)T(n-1) = 2\sum\limits_{i=1}^{n-2}T(i)+c(n-1)^2 \tag2$

为了灭掉 $T(i)$ ， $(1)-(2)$ 得：
$nT(n)-(n-1)T(n-1)=2T(n-1)+c_1n$
也就是：
$nT(n)=(n+1)T(n-1)+c_1n \tag3$

对 $(3)$ 两边同时除以 $n(n+1)$ 得
$\frac{T(n)}{n+1}=\frac{T(n-1)}{n}+\frac{c_1}{n+1} \tag4$

对 $(4)$ 向下写出所有等式：
$\begin{aligned} &\frac{T(n-1)}{n}=\frac{T(n-2)}{n-1}+\frac{c_1}{n}\\ &\frac{T(n-2)}{n-1}=\frac{T(n-3)}{n-2}+\frac{c_1}{n-1}\\ &...\\ &\frac{T(2)}{3}=\frac{T(1)}{2}+\frac{c_1}{3} \\ \end{aligned}$
迭代求解，将这些等式带回去 $(4)$ 得：
$\begin{aligned} \frac{T(n)}{n+1}&=\frac{c_1}{n+1}+\frac{c_1}{n}+\frac{c_1}{n-1}+...+\frac{c_1}{3}+\frac{T(1)}{2}\\ &=c_1(\frac{1}{n+1}+\frac{1}{n}+\frac{1}{n-1}+...+\frac{1}{3}) \end{aligned}$
因为，
$1+\frac{1}{2}+\frac{1}{+}+...+\frac{1}{n}=\ln(n) +C, 其中C为欧拉常数$
所以，
$\frac{T(n)}{n+1} = \Theta(\log n)$
综上，
$T(n) = \Theta(n\log n)$