对我来说,对随机事件的分析,恐怕是最难的。我原以为我数学学得还可以,直到我遇上了随机过程。这篇 blog 所讲的是算法分析,其中涉及到大量对随机情况的分析。因此我在此将其梳理一下,特别注重挖掘不同算法之间的分析过程的相似性。

快速排序是一种原址排序方法,随机化的快排具有 O(nlgn) 的期望运行时间。这个在《算法导论》(第三版)的 7.4.2 节中有一个以比较操作为中心的证明方法。这个证明的核心思想就是:快速排序是由多次 partition 过程组成的,因此关键问题就在于获得 partition 过程的运行时间和运行 partition 过程的次数。partition 过程的最大运行次数是 n-1 次,可以记为 O(n) ,对于其运行时间,练习 7.1-3 给出的结论是 Θ(n) 。这样乍一算,似乎是 O($n^2$) 的时间复杂度。这样计算是错误的,因为 partition 的时间复杂度与其长度有关。这里,我们需要更为细致的分析。决定 partition 运行时间的是其内部循环次数。这个循环次数可以统计每次必须运行的比较次数而得到。通过计算整个 quicksort 的比较次数,我们就可以得到真正的 partition 循环次数。而这个比较次数的期望值,可以通过拆分成示性随机变量相加得到。这个分析的精华之处就在于分析出每两个元素进行比较的概率。很有意思,可以进行比较的组合是 Θ($n^2$) ,但是最终全部比较次数的期望是 O(n lgn)

当然这个只是作为复习,不是今天的重点。这个方法实在是太不直观了点。这次我们用类似于 merge-sort 的分析方法进行分析。

快速排序分析

按照 merge-sort 的分析思路,quicksort 是将一个问题拆分成了两个子问题,但是由于子问题大小不是固定的,这时候就只能分析运行时间的期望。随机化的快速排序使得任何一个元素成为主元都是等可能的。因此我们有如下式子:

$$\begin{aligned} E[T(n)] & = E \left[ \sum^{n}_{q=1} X_q \left( T(q-1) + T(n-q) + \Theta (n) \right) \right] \\ & = \frac{2}{n} \sum^{n-1}_{q=2} E[T(q)] + \Theta (n) \end{aligned}$$

随后,可以通过代入法,把 n lgn 代入 T(n)。其中,有如下不等式可以利用:

$$\begin{equation} \sum^{n-1}_{k=2} k \log k \le \frac{1}{2} n^2 \log n - \frac{1}{8} n^2 \end{equation}$$

由于这个不等式的天赐特性,我们只能记住,有如(1)式的结论就是 O(n lgn)

二叉搜索树分析

我们知道,二叉搜索树的动态操作时间复杂度是 O(h) 。但是对于随机构建的二叉搜索树来说,其期望树高是 O(n lgn) ,对于随机构建的二叉搜索树来说。这里我们证明的是一个稍弱于此定理的定理:随机构建的二叉搜索树的平均节点深度为 O(n lgn)

为表示每一个节点的深度,我们记树T的节点x的深度为 d(x, T) ,而全部节点的深度之和记为 P(T) 。节点平均深度可以表示为

$$\begin{equation} \frac{1}{n} \sum_{x \in T} d(x, T) = \frac{1}{n} P(T) \end{equation}$$

而每一棵树可以拆分为节点与左子树、右子树。我们需要注意,当把 P(T) 拆分为$P(T{left})$和$P(T{right})$之后深度还应该增加当前树总节点再减一。也就是

$$\begin{equation} P(T)=P(T_{left})+P(T_{right})+n-1 \end{equation}$$

对于某一棵树确实是这样。但是这棵树是随机构建的。如何表示出 P(T) 的期望值?事实上,这里和快速排序一样,在随机构建的过程中,第一个元素总是根节点,每一个元素成为第一个元素的概率都是相等的。因此,我们可以据此写出:

$$\begin{equation} E[P(n)]=E\left[ \frac{1}{n} \sum_{k=0}^{n-1}(P(k)+P(n-k-1)+n-1)\right] \end{equation}$$

其中 P(n) 是具有 n 个节点的树高。这时候,我们发现,这和在快速排序那里推导出来的式子是非常相似的。因此,延续着快排分析的思路,可以分析出 P(n) = O(n lgn)。

知道这一点有什么用呢?当构建一棵二叉搜索树时,第一个元素会被选为根节点,其后的元素,每一个都要和其比较。这和快速排序的比较次数是一样的。因为当一个元素选为主元的时候,其后的每一个元素都要和其比较。这样,当用相同的序列构建二叉搜索树和进行快速排序的时候,他们所需要的比较次数是相同的。


留言