二叉搜索树与快速排序的内在相似性

对我来说，对随机事件的分析，恐怕是最难的。我原以为我数学学得还可以，直到我遇上了随机过程。这篇 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 是将一个问题拆分成了两个子问题，但是由于子问题大小不是固定的，这时候就只能分析运行时间的期望。随机化的快速排序使得任何一个元素成为主元都是等可能的。因此我们有如下式子：

E[T(n)]=E[∑q=1nXq(T(q−1)+T(n−q)+Θ(n))]=2n∑q=2n−1E[T(q)]+Θ(n)\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)。其中，有如下不等式可以利用：

∑k=2n−1klog⁡k≤12n2log⁡n−18n2 \sum^{n-1}_{k=2} k \log k \le \frac{1}{2} n^2 \log n - \frac{1}{8} n^2

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

二叉搜索树分析

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

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

1n∑x∈Td(x,T)=1nP(T) \frac{1}{n} \sum_{x \in T} d(x, T) = \frac{1}{n} P(T)

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

P(T)=P(Tleft)+P(Tright)+n−1 P(T)=P(T_{left})+P(T_{right})+n-1

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

E[P(n)]=E[1n∑k=0n−1(P(k)+P(n−k−1)+n−1)] E[P(n)]=E\left[ \frac{1}{n} \sum_{k=0}^{n-1}(P(k)+P(n-k-1)+n-1)\right]

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

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


留言

▲