Problem 1 (教材习题 8-1)

（比较排序的概率下界） 在这一问题中，我们将证明对于给定的 $n$ 个互异的输入元素，任何确定或随机的比较排序算法，其概率运行时间都有下界 $\Omega(n\log n)$ 。首先来分析一个确定的比较排序算法 $A$ ，其决策树为 $T_A$ 。假设 $A$ 的输入的每一种排列情况都是等可能的。

1. 假设 $T_A$ 的每个叶结点都标有在随机输入情况下到达该结点的概率。证明：恰有 $n!$ 个叶结点标有 $1/n!$ ，其他的叶结点标记为 $0$ 。

2. 定义 $D(T)$ 表示一棵决策树 $T$ 的外部路径长度，即 $D(T)$ 是 $T$ 的所有叶结点深度的和。假设 $T$ 为一棵有 $k > 1$ 个叶结点的决策树， $LT$ 和 $RT$ 分别是 $T$ 的左子树和右子树。证明： $D(T)=D(LT) + D(RT) + k$ 。

3. 定义 $d(k)$ 为所有具有 $k > 1$ 个叶结点的决策树 $T$ 的最小 $D(T)$ 值。证明： $d(k) = \min\limits_{1\le i\le k-1}{d(i) + d(k-i) + k}$ 。（提示：考虑一棵有 $k$ 个叶结点的决策树 $T$ 。设 $i$ 是 $LT$ 中的叶结点数，则 $k - i$ 是 $RT$ 中的叶结点数。）

4. 证明：对于给定的 $k(k>1)$ 和 $i(1\le i\le k-1)$ ，函数 $i\log i + (k-i)\log(k-i)$ 在 $i = k/2$ 处取得最小值，并有结论 $d(k) = \Omega(k\log k)$ 。

5. 证明： $D(T_A) = \Omega(n!\log (n!))$ ，并得出在平均情况下，排序 $n$ 个元素的时间代价为 $\Omega(n\log n)$ 这一结论。

现在来考虑一个随机化的比较排序 $B$ 。通过引入两种结点，我们可以将决策树模型扩展来处理随机化的情况。这两种结点是：普通的比较结点和“随机化”结点。随机化结点刻画了算法 $B$ 中所做的形如 RANDOM($1, r$) 的随机选择情况。该类结点有 $r$ 个子结点，在算法执行过程中，每一个子结点等概率地被选择。

6. 证明：对任何随机化的比较排序算法 $B$ ，总存在一个确定的比较排序算法 $A$ ，其期望的比较次数不多于 $B$ 的比较次数。

Solution

1. 因为输入的 $n$ 个元素是互异的，所以它们一共有 $n!$ 种不同的排列。由于 $A$ 的输入的每一种排列情况都是等可能的，则每种排列出现的概率为 $1 / n!$ 。上述的每一种输入的排列情况都对应着 $T_A$ 中的一个概率为 $1 / n!$ 的叶结点，因为算法 $A$ 应该能够区分这些情况。此外，由于这 $n!$ 个标有 $1 / n!$ 的叶结点的概率和已经是 $1$ 了，其他叶结点的概率为 $0$ 。

决策树并不一定每个叶结点都是可达的，但是正确的比较排序算法的决策树可达的叶结点至少得有 $n!$ 个。

2. 不难看出，$LT$ 和 $RT$ 的叶结点深度都恰好比 $T$ 少 $1$ ，记 $L(T)$ 表示 $T$ 的叶结点的集合， $D_T(l)$ 表示叶结点 $l$ 在 $T$ 中的深度，则不难有 $\forall l \in L(LT), D_T(l) = D_LT(l) + 1$ ， $\forall l \in RT, D_T(l) = D_RT(l) + 1$ 。从而

$\begin{aligned}$
D(T) &= \sum_{l\in L(T)} D_T(l)\
&= \sum_{l \in L(LT)} D_T(l) + \sum_{l \in L(RT)} D_T(l)\
&= \sum_{l \in L(LT)} (D_LT(l) + 1) + \sum_{l \in L(RT)} (D_LT(l) + 1)\
&= \sum_{l \in L(LT)} D_LT(l) + \sum_{l \in L(RT)} D_RT(l) + \sum_{l \in L(T)} 1\
&= D(LT) + D(RT) + k
\end{aligned}

3. 根据 $d(k)$ 的定义和第 2 问结论，有

$\begin{aligned}$
d(k) &= \min_{|L(T)| = k}{D(T)}\
&= \min_{|L(LT)| + |L(RT)| = k}{D(LT) + D(RT) + k}\
&= \min_{1\le i \le k-1}{d(i) + d(k-i) + k}
\end{aligned}

4. 令 $f(i) = i\log i + (k-i)\log(k-i)$ ，令

$f'(i) = \frac{1}{\ln 2} + \log i - \frac{1}{\ln 2} - \log(k-i) = \log(\frac{i}{k-i}) = 0$

不难得到，$f(i)$ 在 $i = k / 2$ 时取到最小值 $f(k/2)= k\log(k/2) = k\log k - k$ 。接下来我们可以归纳证明 $d(k) \ge k\log k$ 。

归纳基础：$k = 1$ 时显然成立。

归纳假设：假设 $\forall i < k, d(i) \ge i\log i$ 。

归纳步骤：根据归纳假设，有 $d(i) \ge i\log i$ ， $d(k-i) \ge (k-i)\log (k-i)$ ，则

$\begin{aligned}$
d(k) &= \min_{1\le i \le k-1}{d(i) + d(k-i) + k}\
&\ge \min_{1 \le i \le k-1}{i\log i + (k-i)\log (k-i)} + k\
&= \min_{1 \le i \le k-1} f(i) + k\
&= k\log k - k + k\
&= k\log k
\end{aligned}

综上， $d(k) \ge k\log k$ ，即 $d(k) = \Omega(k\log k)$ 。

5. 由于 $T_A$ 有至少有 $n!$ 个叶结点，我们有 $D(T_A) \ge d(n!) = \Omega(n!\log(n!))$ ，即 $D(T_A) = \Omega(n!\log(n!))$ 。平均情况下，根据第 1 问结论，到达这 $n!$ 个叶结点的概率都是 $1 / n!$ ，运行时间就是从根结点到叶结点的路径的期望长度，即
   $\frac{D(T_A)}{n!} = \frac{\Omega(n!\log(n!))}{n!} = \Omega(\log(n!)) = \Omega(n\log n)$

   所以，平均情况运行时间为 $\Omega(n\log n)$ 。

6. 由于平均情况运行时间已经是输入元素的所有 $n!$ 种排列下的平均时间了，随机化算法的期望时间只会在平均情况运行时间之上增加手动引入随机性所消耗的时间，而不可能改进平均情况运行时间。因此，随机算法的期望运行时间只会比确定性算法的平均情况运行时间在低阶项和常数系数上更糟糕，在渐近意义上最多同阶。

Problem 2 (教材习题 8-2)

（线性时间原址排序） 假设有一个包含 $n$ 个待排序数据记录的数组，且每条记录的关键字的值为 $0$ 或 $1$ 。对这样一组记录进行排序的算法可能具备如下三种特性中的一部分：

• 算法的时间代价是 $O(n)$ 。

• 算法是稳定的。

• 算法是原址排序，除了输入数组之外，算法只需要固定的额外存储空间。

1. 给出一个满足上述第 1 个条件和第 2 个条件的算法。

2. 给出一个满足上述第 1 个条件和第 3 个条件的算法。

3. 给出一个满足上述第 1 个条件和第 2 个条件的算法。

4. 第 1 问到第 3 问中的算法中的任一个是否可以用于 RADIX-SORT 的第 2 行作为基础排序方法，从而使 RADIX-SORT 在排序有 $b$ 位关键字的 $n$ 条记录时的时间代价是 $O(bn)$ ？如果可以，请解释应如何处理；如果不行，请说明原因。

5. 假设有 $n$ 条记录，其中所有关键字的值都在 $1$ 到 $k$ 的区间内。你应该如何修改计数排序（见第7讲PPT第11页），使得它可以在 $O(n+k)$ 时间内完成对 $n$ 条记录的原址排序。除输入数组外，你可以使用 $O(k)$ 大小的额外存储空间。你给出的算法是稳定的吗？（提示：当 $k = 3$ 时，你该如何做？）

Solution

1. 计数排序——稳定且线性时间。

2. 快速排序的划分子过程——线性时间且原址排序。随便选取 0 或者 1 为主元即可将 0-1 数组排序。

3. 插入排序——稳定且原址排序。

4. 根据引理8.3（见第7讲PPT第18页），使得基数排序呈线性复杂度的内部排序必须是稳定的、线性时间的，因此只有第 1 问中给出的算法满足条件，第 2 、 3 问中的不满足。

5. 基本思路：用 $O(k)$ 的额外数组 $B$ 来记录输入元素的个数；和计数排序一样，用 $O(k)$ 的额外数组 $C$ 来记录各个元素在输出数组中的位置；根据 $C$ 记录的位置，将 $B$ 中记录的剩余个数不为 $0$ 的元素放到 $A$ 的对应位置上输出。伪代码如下：

这样我们便完成只需要 $O(k)$ 大小（$k$ 是常数）额外空间的原址排序，且时间复杂度为 $O(n+k)$ （第 14 到 15 行的循环体最多执行 $n$ 次，虽然它放在了一个 $0$ 到 $k$ 的 for 循环当中）。

但这个算法就不是稳定排序了，因为数组 $B$ 只保存了元素的个数，没有保存元素的顺序。

Problem 3 (教材习题 8-3)

（变长数据项的排序）

1. 给定一个整数数组，其中不同的整数所包含的数字的位数（不含前导 0 ）可能不同，但该数组中，所有整数中包含的总数字位数为 $n$ 。设计一个算法，使其可以在 $O(n)$ 时间内对该数组进行排序。

2. 给定一个字符串数组，其中不同的字符串所包含的字符数可能不同，但所有字符串中的总字符个数为 $n$ 。设计一个算法，使其可以在 $O(n)$ 时间内对该数组排序。（注意：此处的顺序是指标准的字典序，例如 $a < ab < b$ 。）

Solution

1. 使用桶排序内嵌基数排序即可。根据整数的位数不同建立不同的桶，因为位数少的数字一定小于位数多的数字（不含前导 0 ）。然后，每个桶的内部位数相同，使用基数排序即可。

   • 下面说明复杂度为 $O(n)$ ：

   • 一个具有 $k$ 个 $d$ 位十进制整数的桶进行基数排序的复杂度为 $O(kd)$ ，可以根据引理 8.3 (详见第7讲PPT第18页) 很容易得到，而 $k$ 个 $d$ 位数的数位和恰好就是 $kd$ 。

   • 因此，任意一个桶的基数排序复杂度都是这个桶中的整数的总位数。从而，所有的桶都排好序的复杂度就是所有桶中整数的总位数，即 $O(n)$ 。

2. 这一问可以和上一问类似处理，因为一个字符串可以视作一个 26 进制数（假设只有 26 个英文字母）。

   • 也可以先按照首字母排序，然后对除了首字母以外的子串递归的排序，但是如果剩余的子串是空串的话，则不参与递归。

Problem 4 (教材习题 8-4)

（水壶） 假设给了你 $n$ 个红色的水壶和 $n$ 个蓝色的水壶。它们的形状和尺寸都各不相同。所有红色水壶中所盛的水都不一样多，蓝色水壶也是如此。而且，对于每一个红色水壶来说，都有一个对应的蓝色水壶，两者盛有一样多的水；反之亦然。

你的任务是找出所有的所盛水量一样多的红色水壶和蓝色水壶，并将它们配成一对。为此，可以执行如下操作：挑出一对水壶，其中一个是红色的，另一个是蓝色的，将红色水壶中倒满水，再将水倒入蓝色的水壶中。通过这一操作，可以判断出这个红色水壶是否比蓝色水壶盛的水更多，或者两者是一样多的。假设这样的比较需要花费一个单位时间。你的目标是找出一个算法，它能够用最少的比较次数来确定所有水壶的配对。注意，你不能直接比较两个红色或者两个蓝色的水壶。

1. 设计一个确定性算法，它能够用 $\Theta(n^2)$ 次比较来完成所有水壶的配对。

2. 证明：解决该问题算法的比较次数下界为 $\Omega(n\log n)$ 。

3. 设计一个随机算法，其期望的比较次数为 $O(n\log n)$ ，并证明这个界是正确的。对你的算法来说，最坏情况下的比较次数是多少？

Solution

1. 任意选择一个红色水壶，将它和所有的蓝色水壶比较，直到找到盛水量一样多的蓝色水壶为止。然后将这两个水壶单独放在一边，对剩余的 $2n-2$ 个水壶重复上述过程，直至全部配对为止。

   • 这最多需要 $\sum\limits_{i=1}^{n-1} i = n(n-1)/2 = \Theta(n^2)$ 次比较。

2. 我们可以先固定红色水壶的顺序，由于所有水壶的水都不一样多，问题就变成了寻找蓝色水壶的一个排列，使得第 $i$ 个蓝色水壶的大小和第 $i$ 个红色水壶相同。于是，这个问题就变成了将任意排列的蓝色水壶调整为一个特定排列的问题，这与排序问题本质上是一致的。因为排序问题相当于将任意排列的输入序列调整为顺序序列这一特定排列。因此，不难得到，解决该问题算法的比较次数下界和排序问题一致，为 $\Omega(n\log n)$ 。

   • 具体地，我们可以构造一棵决策树来表示蓝色水壶和红色水壶之间的比较。

   • 一个内部结点代表了一组特定的红色水壶与蓝色水壶的一次比较；一个叶结点代表了基于比较结果的蓝色水壶的排列。

   • 我们关心一个蓝色水壶和一个红色水壶相比是更小、相等还是更大，因此每个节点应该有 $3$ 个子结点。

   • 由于一个正确的算法需要处理所有可能的情况，因此至少 $n!$ 个叶结点，也就是说决策树的高度至少是 $\log_3(n!) = \Theta(n\log n)$ ，从而解决该问题的比较算法的比较次数下界为 $\Omega(n\log n)$ 。

3. 我们可以使用一个类似于随机化快速排序的算法来解决该问题。

   • 随机选择一个红色水壶作为主元，将所有的蓝色水壶划分为比该红色水壶小的，和该红色水壶相等的，以及比该红色水壶更大的三个部分，该划分过程需要 $O(n)$ 次比较。

   • 划分结束后，递归地解决比主元小的和比主元大的蓝色水壶组成的两个子问题即可。该算法的过程和随机化的快速排序别无二致，因此期望比较次数为 $O(n\log n)$ （详见第6讲PPT第29页），最坏情况下的比较次数为 $O(n^2)$ （详见第6讲PPT第20页）。