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

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

【算法笔记】差消法化简高阶递推方程示例：计算快速排序平均时间复杂
【算法笔记】递归树应用实例：计算归并排序平均时间复杂度
快速排序与归并排序Java实现版
快速排序
Partition 快排核心函数
快速排序
day09-冒泡排序+优化
排序算法
常用排序算法
快速排序（1）

快速排序代码如下：

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)$

参考资料：https://www.icourse163.org/course/PKU-1002525003

【算法笔记】差消法化简高阶递推方程示例：计算快速排序平均时间复杂
快速排序代码如下：每一趟的工作量 = 子问题的工作量 + 划分的工作量（即划分的比较次数）下图展示了n种可能的输...
【算法笔记】递归树应用实例：计算归并排序平均时间复杂度
递归树递归树是迭代的图形表示，可用于求解递推方程。例1：利用递归树计算归并排序的平均时间复杂度。归并排序伪代...
快速排序与归并排序Java实现版
快速排序快速排序（Quicksort）是一种排序算法，平均时间复杂度为：O(n log n)，最坏需要 O(n...
快速排序
描述快速排序算是用得比较多的排序算法，很多库的排序方法都是用的快速排序，快速排序的平均时间复杂度为O（NlogN...
Partition 快排核心函数
快速排序介绍快速排序是目前在实践中非常高效的一种排序算法，它不是稳定的排序算法，平均时间复杂度为O(nlogn)...
快速排序
快速排序快速排序是一种不稳定的排序算法，平均时间复杂度为O(n*logn)。快速排序使用分治法(Divide a...
day09-冒泡排序+优化
排序算法（SortAlgorithm）算法时间复杂度总结：排序方法时间复杂度（平均）时间复杂度（最坏）时间复杂...
排序算法
快速排序对于快速排序需要了解快速排序的平均复杂度？最坏复杂度？是否是稳定排序？快速排序也是一种分治算法归并排...
常用排序算法
排序插入排序、冒泡排序、归并排序、快速排序，选择排序算法的比较，需要从额外空间消耗，平均时间复杂度和最差时间复...
快速排序（1）
快速排序是经典的排序算法，最理想的情况下，时间复杂度近乎二分法，平均时间复杂度为O（nlogn）关于快速排序的图解...