文章目录
  1. 1. 最坏情况分析
  2. 2. 证明快速排序的最佳运行时间为$\Omega (nlgn)$

快排恐怕是最重要的一种排序了。在算法一书中,对于其证明,只有蜻蜓点水轻轻一过。这里整理下来自CLRS的快排证明。

最坏情况分析

利用代换法,可以证明快速排序的运行时间为$O(n^2)$。设T(n)是过程QUICKSORT作用于规模为n的输入上的最坏情况时间,则有:

$$T(n) = \max(T(q)+T(n-1-1))+\theta (n) (0\leq q\leq n-1)
$$

其中参数q由0到n-1,这是因为过程PARTITION产生两个子问题,总的大小为n-1。我们猜测$T(n) \leq cn^2$成立,c为某个常数。将此式带入递归式(7.1),得:

$$
T(n) \leq \max(cq^2+c(n-q-1)^2)+\theta(n) \\
= c \times \max(q^2+(n-q-1)^2)+\theta(n)
$$

我们先观察$max(q^2+(n-q-1)^2)$,化简开来即$2q^2+2q-2nq+…$。对称轴$\frac{n-1}{2}$,落入区间[0,n-1]中。函数在区间的两头取最大值。所以原式可化简为

$$
c \times max(q^2+(n-q-1)^2)+\theta(n) \\
\leq c(n-1)^2+\theta(n)\\
= cn^2-2cn+c+\theta(n)\\
\leq cn^2(c足够小)
$$

同样的,可以证明快排的最坏运行时间为$\Omega(n^2)$

猜测$T(n) \geq cn^2-2n $

$$
T(n) = \max(T(q)+T(n-q-1))+\theta (n) (0\leq q\leq n-1) \\
= \max(cq^2-2q+c(n-q-1)^2-2(n-q-1))+\theta(n) \\
= \max(cn^2 -2n+ c(n-q-1)^2+2)+\theta(n)\\
\geq cn^2-2n
$$

证明快速排序的最佳运行时间为$\Omega (nlgn)$

猜测$T(n) \geq nlgn $

$$
T(n) = \min(T(q)+T(n-q-1))+\theta (n) (0\leq q\leq n-1) \\
\geq c(\min(qlgq+(n-q-1)lg(n-q-1)))+\theta (n)\\
\geq c((n-1)lg\frac{n-1}{2}) + \theta(n) \\
= c(nlg\frac{n-1}{2} - lg\frac{n-1}{2})+\theta(n) \\
= c(nlgn + nlg(\frac{n-1}{2n}) - lg\frac{n-1}{2})+\theta(n) \\
= cnlgn + c(nlg(\frac{n-1}{2n}) - lg\frac{n-1}{2})+\theta(n) \\
\geq cnlgn + c(-n-lg\frac{n-1}{2})+\theta(n)
\geq cnlgn (c够小即可)
$$

文章目录
  1. 1. 最坏情况分析
  2. 2. 证明快速排序的最佳运行时间为$\Omega (nlgn)$