Problem 1 (教材习题 7.2-5)

假设快速排序的每一层所做的划分的比例都是 $1-\alpha : \alpha$ ，其中 $0 < \alpha \le 1/2$ 且是一个常数。试证明：在相应的递归树中，叶结点的最小深度大约是 $- \log n / \log\alpha$ ，最大深度大约是 $-\log n / \log(1-\alpha)$ （无需考虑舍入问题）。

Solution

证明：递归树的最小深度相当于：每次都选择最小的子问题，需要多少次才能到达基础情况，假设需要 $k$ 次，由于 $0 < \alpha \le 1/2$ ，即 $\alpha < 1 - \alpha$ ，我们每次都应该选择规模为 $\alpha\cdot n$ 的子问题，才能更快到达基础情况，具体地： $\alpha^k\cdot n \approx 1$，即

$k \approx \log_{\alpha}(1 / n) = - \log n / \log\alpha$

递归树的最大深度相当于：每次都选择最大的子问题，需要多少次才能到达基础情况，假设需要 $k$ 次，和之前类似，我们很容易得到 $(1 - \alpha)^k \cdot n \approx 1$ ，即

$k \approx \log_{1-\alpha}(1/n) = -\log n / \log(1-\alpha)$

Problem 2 (教材习题 7.2-6)

试证明：在一个随机输入的数组上，对于任何常数 $0 < \alpha \le 1/2$ ，PARTITION 产生比 $1 - \alpha : \alpha$ 更平衡的划分的概率约为 $1 - 2\alpha$ 。

Solution

证明：考虑产生一个更糟糕的划分的概率，为了产生一个比 $1 - \alpha : \alpha$ 更糟糕的划分， PARTITION 算法必须选择前 $\alpha n$ 小的或者前 $\alpha n$ 大的元素作为主元，这两者的概率都约为 $\alpha n / n = \alpha$ ，于是产生一个更糟糕的划分的概率是 $\alpha + \alpha = 2\alpha$ 。从而，产生一个更平衡的划分的概率约为 $1 - 2 \alpha$ 。

Problem 3 (教材习题 7.4-1改)

证明：在递归式

$T(n) = \max_{0 \le q \le n - 1}(T(q) + T(n - q - 1)) + \Theta(n)$

中， $T(n) = \Theta(n^2)$ 。

Solution

证明：不失一般性，将递归式改写为 $T(n) = \max_{0 \le q \le n - 1}(T(q) + T(n - q - 1)) + dn$ ，下面使用代入法证明 $T(n) = \Theta(n^2)$ 。

先证 $T(n) = O(n^2)$ 。假设 $T(n) \le cn^2$ ，代入递归式有：

$\begin{aligned}$
T(n) &\le \max_{0 \le q \le n - 1}(cq^2 + c(n - q - 1)^2) + dn\
&= c\max_{0 \le q \le n - 1}(q^2 + (n - q - 1)^2) + dn\
&= c(n-1)^2 + dn\
&= cn^2 + (d - 2c)n + c\
&\le cn^2
\end{aligned}

其中，倒数第 3 步是二次函数的区间最值，最后一步取 $c \ge d/2, n \ge c / (2c-d)$ 即可。

再证 $T(n) = \Omega(n^2)$ 。假设 $T(n) \ge cn^2$ ，代入递归式有：

$\begin{aligned}$
T(n) &\ge \max_{0 \le q \le n - 1}(cq^2 + c(n - q - 1)^2) + dn\
&= c\max_{0 \le q \le n - 1}(q^2 + (n - q - 1)^2) + dn\
&= c(n-1)^2 + dn\
&= cn^2 + (d - 2c)n + c\
&> cn^2
\end{aligned}

其中，最后一步取 $0 < c < d/2$ 即可。

综上， $T(n) = \Theta(n^2)$ 。

Problem 4 (教材习题 7.4-5)

当输入数据已经“几乎有序”时，插入排序速度很快。在实际应用中，我们可以利用这一特点来提高快速排序的速度。当对一个长度小于 $k$ 的子数组调用快速排序时，让它不做任何排序就返回。当上层的快速排序调用返回后，对整个数组运行插入排序来完成排序过程。试证明：这一排序算法的期望时间复杂度为 $O(nk + n\log(n/k))$ ；并说明我们应该如何选择 $k$ 。

Solution

证明：快速排序的期望时间复杂度和每次划分都平衡的最好时间复杂度是同阶的，因此我们不妨设每次划分都是平衡的，求得的复杂度就是期望复杂度。记运行时间为 $T(n)$ ，则题设算法的递归式为

$T(n) = \begin{cases}$
2T(n/2) + O(n), & n > k\
O(n^2), & n <= k
\end{cases}

用递归树法不难发现，递归树一共有 $\log(n/k) + 1$ 层，内部结点每层的代价为 $O(n)$ ；有 $n/k$ 个叶子结点，每个叶子结点的代价为 $O(k^2)$ ，则总代价为递归树所有内部结点和叶子结点的代价和，为

$\log(n / k)\cdot O(n) + (n / k)\cdot O(k^2) = O(nk + n\log(n/k))$

对于 $k$ 的选择，我们的原则是复杂度优于直接快排的 $O(n\log n)$ 即可，不过这里由于渐近记号隐藏了系数，会导致不等式无解，我们记插入排序的复杂度系数为 $c_i$ ，快速排序的复杂度系数为 $c_q$ ，则需要

$c_q n\log n > c_i nk + c_q n\log(n/k) \Leftrightarrow \frac{\log k}{k} > \frac{c_i}{c_q}$

取满足上述不等式条件的 $k$ 即可。不过在编程实践中，如果要这样处理，我们通常是根据具体的实验数据来选取一个合适的 $k$ 的。

Problem 5 (教材习题 7.4-6)

考虑对 PARTITION 过程做这样的修改：从数组 $A$ 中随机选出三个元素，并用这三个元素的中位数（即这三个元素按大小排在中间的值）对数组进行划分。求以 $a$ 的函数形式表示的、最坏划分比例为 $\alpha : (1-\alpha)$ 的近似概率，其中 $0 < \alpha < 1$ 。

Solution

不失一般性，假设数组 $A$ 中的元素是 $1, 2,\cdots, n$ 的一个排列。令 $k$ 是随机选出三个数字中的中位数，不妨设 $\alpha \le 1 / 2$ ，则最坏划分比例为 $\alpha : (1-\alpha)$ 的概率为 $\alpha n \le k \le (1-\alpha)n$ 的概率。

考虑相反事件，即 $k < \alpha n$ 或者 $k > (1-\alpha)n$ ，其概率相当于随机选出三个元素，至少有两个在 $[1, \alpha n]$ 中或者至少有两个在 $[(1-\alpha)n, n]$ 中的概率，并且这两件事情概率是相等的，都是

$3\alpha^2(1-\alpha) + \alpha^3 = 3\alpha^2 - 2\alpha^3$

于是，最坏划分比例为 $\alpha : (1-\alpha)$ 的概率为 $1 - 2(3\alpha^2 - 2\alpha^3) = 1 - 6\alpha^2 + 4\alpha^3$ 。