Analisis of Random QuickSort

数学 CLRS

---

随机化快排与普通快排唯一的不同是，随机化要求随机选取一个元素(有可能就为头元素)与头元素交换后，再进行“普通”快排。我们想证明随机化快排能保证运行时间在平均运行时间:

$$\theta(nlgn)$$
证明:

我们先定义一个随机变量T(n)，表示算法的运行时间

$$T(n) =r.var\ for\ running\ time\ assuming\ r.nums\ indep.$$
这里需要注意的是，只有当这些随机数(每个选择主元的事件)相互独立时，等式才成立

为了进行分析，我们首先得知道该选择哪个元素作为主元。

令主元的下标为k，在我们一个特定划分的情况下能得到一个 指示器随机变量(indicator-random-variable) Xk

$$X_k=\begin{cases} 1,\ if\ partition\ generate\ k:n-k-1\ split\\ 0,\ otherwise\\ \end{cases} \ \ \ (for\ k=0, 1...n-1)$$

对这个特定k的 k : n-k-1 划分，我们给予值 1，对于其他情况，我们给予值0.

则Xk的期望(生成一次 k : n-k-1 划分的概率)为

$$\begin{align} E[X_k]&=0·Pr\{X_k=0\}+1·Pr\{X_k=1\}\\ &=Pr\{X_k=1\}\\ &=1/n\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (每个数有1/n的几率被选为主元) \end{align}$$
对于T(n)我们则有
$$T(n)=\begin{cases} T(0)+T(n-1)+\theta(n),\ \ if\ 0:n-1\ split\\ T(1)+T(n-2)+\theta(n),\ \ if\ 1:n-2\ split\\ ...\\ T(n-1)+T(0)+\theta(n),\ \ if\ n-1:0\ split\\ \end{cases}$$
这就是T(n)的递归，而每次递归总有n种情况

对于这种麻烦情况，指示器随机变量便体现出了他的优雅，实际上T(n)便等于

$$T(n)=\sum_{k=0}^{n-1}X_k[T(k)+T(n-k-1)+\theta(n)]$$
此时我们便可开始求T(n)的期望
$$\begin{align} E[T(n)]&=E\{\sum_{k=0}^{n-1}X_k[T(k)+T(n-k-1)+\theta(n)]\}\\ &=\sum_{k=0}^{n-1}E\{X_k[T(k)+T(n-k-1)+\theta(n)]\}\\ &=\sum_{k=0}^{n-1}E[X_k]E[T(k)+T(n-k-1)+\theta(n)]\\ &=\frac{1}{n}\sum_{k=0}^{n-1}E[T(k)+T(n-k-1)+\theta(n)]\\ &=\frac{1}{n}\sum_{k=0}^{n-1}E[T(k)]+\frac{1}{n}\sum_{k=0}^{n-1}E[T(n-k-1)]+\frac{1}{n}\sum_{k=0}^{n-1}\theta(n)\\ &=\frac{2}{n}\sum_{k=0}^{n-1}E[T(k)]+\theta(n)\\ &=\frac{2}{n}\sum_{k=2}^{n-1}E[T(k)]+\theta(n)\\ \end{align}$$

解释:
(5)~(6): 因为$X_k$独立于任何其他分化存在(不受分化方式的影响)，所以可分别求期望后相乘.If you will,the $X_k$ that would exist for any of the other recursive calls.
(7)~(8):期望的线性性质。
(8)~(9): 其实 $\frac{1}{n}\sum_{k=0}^{n-1}E[T(k)]=\frac{1}{n}\sum_{k=0}^{n-1}E[T(n-k-1)]$，可以分别写出累加的前几项，发现只是加的顺序反了过来，所以可以合并
(9)~(10):累加的前两项，即T(0)、T(1)为 $\theta(1)$的复杂度，为了之后方便运算，提取出来与后方的 $\theta(n)$合并

得到

$$E[T(n)]=\frac{2}{n}\sum_{k=2}^{n-1}E[T(k)]+\theta(n)$$

我们最终想要证明的是$E[T(n)]\leq anlgn\ ,\ for\ any\ a.$

证明之前需要先知道一个定理（这里先不给出证明）:

$$\sum_{k=2}^{n-1}klgk\leq \frac{1}{2}n^2lgn-\frac{1}{8}n^2$$
然后我们便可运用代换法(substitution) 证明随机化快排的时间复杂度:
$$\begin{align} Let\ E[T(n)]&\leq \frac{2}{n}\sum_{k=2}^{n-1}aklgk+\theta(n)\\ &\leq \frac{2a}{n}(\frac{1}{2}n^2lgn-\frac{1}{8}n^2)+\theta(n)\ (由上述定理)\\ &=anlgn-(\frac{an}{4}-\theta(n)) \end{align}$$
当a足够大时
$$E[T(n)]\leq anlgn$$
即
$$T(n)=\theta(nlgn)$$
证毕.