算法导论 7 Problems 答案

7-1

a

可以知道，此时支点值 $x$ 为 $13$。

$\begin{array}{|ccc|}\hline & i& j\\ ⟨13,19,9,5,12,8,7,4,11,2,6,21⟩\\ ⟨\underset{―}{6},19,9,5,12,8,7,4,11,2,\underset{―}{13},21⟩& 1& 13\\ ⟨6,\underset{―}{2},9,5,12,8,7,4,11,\underset{―}{19},13,21⟩& 2& 10\\ ⟨6,2,9,5,12,8,7,4,\underset{―}{11},19,13,21⟩& 10& 9\\ \hline\end{array}$

b

当数组中所有元素都相等时，HOARE-PARTITION 将会返回 $\lfloor {\displaystyle \frac{p+r}{2}}\rfloor$，也就是中间值。这个算法相比于普通的 PARTITION，其将各个元素划分地更加均匀，使得快速排序算法的时间复杂度得以下降至最好。

c

一开始时，$i=p-1,j=r+1$ 成立，恰好在数组的左侧和右侧。直到开始访问数组时，数组指针 $i,j$ 先向中间靠拢。当 $A[j]>x$ 时，$j$ 将一直左移；当 $A[i]<x$ 时，$i$ 将一直右移。由于一个数 $u$ 不可能同时大于一个数 $v$，并且小于 $v$，因此当 $i,j$ 相遇时，它们必定停下来。最终，$i,j$ 永远不会越界。

d

根据题目 7-1-c 的结论，$j$ 将会一直在区间 $[p,r]$ 内，哪怕是已经达到 $i>j$。由于 $|A|\ge 2$，那么将会有以下 $2$ 种情况说明 $j<r$：

• $A[p]\ge A[r]$，此时第一轮 while 循环中，两个 repeat 循环各迭代一次后循环立刻停下。交换完成后，由于 $i<j$ 仍然成立，因此外循环仍然不会结束。第二轮循环迭代将会使得 $j$ 再自减 $1$，由此 $j<r$。
• $A[p]<A[r]$，此时第一轮 while 循环中，第一个 repeat 循环将会迭代两次以上，那么就有 $j<r$ 仍然成立。

因此，返回的 $j$ 仍然保证了在区间 $[p,r)$ 中。

e

在每一次迭代前，$\mathrm{\forall }k\in [j+1,r]$，都有 $A[k]\ge x$ 成立，$\mathrm{\forall }k\in [p,j]$，都有 $A[k]\le x$ 成立。当遇到不满足这个情况的数时，两个 repeat 循环都会停下，交换这两个分别不符合各自性质的数，从而维持着它们原本的性质。因此，最终循环终止后，$\mathrm{\forall }k\in [j+1,r]$，都有 $A[k]\ge x$ 仍然成立，$\mathrm{\forall }k\in [p,j]$，都有 $A[k]\le x$ 仍然成立。因此，$A[i:j]$ 中的所有数都不超过 $A[j+1,r]$。

f

HOARE-QUICKSORT(A, p, r)
  if p < r
    q = HOARE-PARTITION(A, p, r)
    HOARE-QUICKSORT(A, p, q)
    HOARE-QUICKSORT(A, q + 1, r)

7-2

a

由于数组中的所有数都一样，算法 RANDOMIZED-PARTITION 的前 2 行将会不会起到任何作用。算法 RANDOMIZED-PARTITION 调用算法 PARTITION 时，PARTITION 将会把所有数都划分到左侧，并且总返回 $r$。因此其运行时间为 $T(n)=T(n-1)+\mathrm{\Theta }(n)=\mathrm{\Theta }(n^2)$。

b

// 返回的两个下标q, t代表着A[p : q - 1], A[q : t], A[t + 1 : r]这三段。
PARTITION'(A, p, r)
  x = A[p]
  i = k = p
  j = r
  while i <= j
    if A[i] < x
      exchange A[i] and A[k]
      i += 1
      k += 1
    else if A[i] == x
      i += 1
    else
      exchange A[i] and A[j]
      j -= 1
  return k, i - 1

可以发现，在每一轮循环中，要么 $i$ 自增 $1$，要么 $j$ 自减 $1$，直到 $i,j$ 相遇。因此算法 PARTITION' 的时间复杂度为 $\mathrm{\Theta }(r-p)$。

c

RANDOMIZED-PARTITION'(A, p, r)
  i = RANDOM(p, r)
  exchange A[r] with A[i]
  return PARTITION'(A, p, r)

QUICKSORT'(A, p, r)
  if p < r
    (q, t) = RANDOMIZED-PARTITION'(A, p, r)
    QUICKSORT'(A, p, q - 1)
    QUICKSORT'(A, t + 1, r)

d

为了方便分析，考虑将算法 PARTITION' 中将 $A[i]$ 和 $x$ 的两次比较统一称为一次比较，因为将 $A[i]$ 和 $x$ 仅需一次比较，就可以得出是小于，等于，还是大于，而为了方便编写伪代码，这里写成了两次比较（在第 5, 8 行分别进行了一次小于和等于的比较。）

假设 $m$ 是数组 $A$ 中不同的数的个数，那么算法 RANDOMIZED-PARTITION' 的调用次数至少为 $m$。

假设数 $x$ 在 $A$ 中的出现次数为 $c(A,x)$。假设数组 $A$ 排序后的结果为 $⟨z_1,z_2,\dots ,z_n⟩$，满足 $z_1\le z_2\le \cdots \le z_n$。

对于 $A$ 中的两个数 $z_i,z_j(i<j)$，如果 $z_i=z_j=x$，那么它们之间有可能发生比较，有可能没有发生比较（取决于支点 $x$ 是否选择自 $z_i$ 或者是 $z_j$，如果是，那么就发生了比较。）无论如何，为 $x$ 的这一些数将会发生 $c(A,x)-1$ 次比较。因此，相同的比较次数为 $O(n)$ 次。

现在假设 $z_i<z_j$，那么如果数 $x$ 满足 $z_i<x<z_j$ 先于 $z_i,z_j$ 被选择，那么 $z_i,z_j$ 将会无法被比较，否则可以被比较。这些 $x$ 的个数有上限 $j-i-1$ 个。

和第 7.4.2 章类似，假设 $X$ 是比较次数，$X_{ij}$ 是元素 $z_i,z_j$ 被比较的概率，那么有 $E[X_{i,j}]\ge {\displaystyle \frac{2}{j-i+1}}$，而不再是等于。

因此，有

$\begin{array}{rl}E[X]& =\sum _{i=1}^{n-1}\sum _{j=i+1}^n{\displaystyle \frac{2}{j-i+1}}\\ & \ge \sum _{i=1}^{n-1}\sum _{k=1}^{n-i}{\displaystyle \frac{2}{k+1}}\\ & \ge \sum _{i=1}^{n-1}\sum _{k=1}^{n-i}{\displaystyle \frac{2}{2k}}& (A)\\ & =\sum _{i=1}^{n-1}\mathrm{\Omega }(\lg n)\\ & =\mathrm{\Omega }(n\lg n)\end{array}$

其中，步骤 $(A)$ 是因为当 $k\ge 1$ 时，${\displaystyle \frac{1}{k+1}}\ge {\displaystyle \frac{1}{2k}}$ 成立。

这说明算法 RANDOMIZED-PARTITION' 的时间复杂度为 $T(n)=\mathrm{\Omega }(n\lg n)$。

根据算法 QUICKSORT' 的第 3, 4 行递归的区间可知，其上限 $T(n)$ 必定不超过算法 RANDOMIZED-QUICKSORT 的上限。

因此，最终有 $T(n)=\mathrm{\Theta }(n\lg n)$。

7-3

a

根据算法 RANDOMIZED-PARTITION 的第一行可以知道，每个元素被选作支点的概率为 ${\displaystyle \frac{1}{n}}$。那么可以得到 $E[X_i]={\displaystyle \frac{1}{n}}$。

b

可以发现，在每次随机选择支点中，最多只有一个支点被选中，因此最多只有一个 $X_q=1$。假设此时选择的支点是第 $q$ 小的，那么就有 $q-1$ 个元素划分至左侧，有 $n-q$ 个元素划分至右侧，产生了大小分别为 $q-1,n-q$ 的子问题。对整个数组进行一次划分的时间复杂度为 $\mathrm{\Theta }(n)$，因此有

$\begin{array}{rl}E[T(n)]& =E[\sum _{q=1}^n{X}_q\cdot (T(q-1)+T(n-q))]+\mathrm{\Theta }(n)\\ & =E[\sum _{q=1}^n{X}_q\cdot (T(q-1)+T(n-q)+\mathrm{\Theta }(n))]\end{array}$

c

假设 $E[T(0)]=0$，因为空数组并不会产生任何的开销。由于随机变量 $X_i$ 和划分后的子问题是独立的，那么有

$\begin{array}{rl}E[T(n)]& =E[\sum _{q=1}^n{X}_q\cdot (T(q-1)+T(n-q)+\mathrm{\Theta }(n))]\\ & =E[\sum _{q=1}^n{X}_q\cdot (T(q-1)+T(n-q))]+\mathrm{\Theta }(n)\\ & =\sum _{q=1}^n(E[X_q]\cdot (E[T(q-1)+T(n-q)]))+\mathrm{\Theta }(n)\\ & =\sum _{q=1}^n({\displaystyle \frac{1}{n}}\cdot (E[T(q-1)]+E[T(n-q)]))+\mathrm{\Theta }(n)\\ & ={\displaystyle \frac{2}{n}}\sum _{q=1}^{n-1}E[T(q)]+\mathrm{\Theta }(n)\end{array}$

d

可以发现，$f(q)=q\lg q$ 是一个递增函数，因此有

$\begin{array}{rl}\sum _{q=1}^{n-1}q\lg q& \le {\int }_1^{n}x\lg xdx\\ & ={{\displaystyle \frac{1}{2}}{x}^2\lg x-{\displaystyle \frac{x^2}{4\ln 2}}|}_1^n\\ & ={\displaystyle \frac{n^2}{2}}\lg n-{\displaystyle \frac{n^2}{4\ln 2}}+{\displaystyle \frac{1}{4\ln 2}}\\ & \le {\displaystyle \frac{n^2}{2}}\lg n-{\displaystyle \frac{n^2}{8}}& (n\ge 2)\end{array}$

当 $n=1$ 时，可以验证原式仍然成立。因此 $\mathrm{\forall }n\ge 1$，都有 ${\displaystyle \sum _{q=1}^{n-1}q\lg q\le {\displaystyle \frac{n^2}{2}}\lg n-{\displaystyle \frac{n^2}{8}}}$。

e

假设 $T(n)\le cn\lg n$，那么联立题目 7-3-c, 7-3-d 的结论，有

$\begin{array}{rl}E[T(n)]& ={\displaystyle \frac{2}{n}}\sum _{q=1}^{n-1}E[T(q)]+\mathrm{\Theta }(n)\\ & \le c\cdot {\displaystyle \frac{2}{n}}({\displaystyle \frac{n^2}{2}}\lg n-{\displaystyle \frac{n^2}{8}})+\mathrm{\Theta }(n)\\ & =cn\lg n-{\displaystyle \frac{cn}{4}}+\mathrm{\Theta }(n)\\ & =cn\lg n-({\displaystyle \frac{cn}{4}}-\mathrm{\Theta }(n))\\ & \le cn\lg n& (A)\end{array}$

其中，变换 $(A)$ 表示假设 ${\displaystyle \frac{cn}{4}}$ 渐进增长上界比 $\mathrm{\Theta }(n)$ 高。

因此，只需要 $c$ 再取好 $c\ge {\displaystyle \frac{T(2)}{2}}$。那么由数学归纳法，$T(n)=O(n\lg n)$ 成立。

7-4

a

考虑使用归纳法的思想证明，将数组前 ${\displaystyle \frac{n}{3}}$，中间 ${\displaystyle \frac{n}{3}}$，后 ${\displaystyle \frac{n}{3}}$ 的区间分别称为数组的左侧，中间，右侧。

当数组长度 $n=r-p+1\le 2$ 时，可以发现这个算法能够正确排序。

当 $r-p+1>2$ 时，第 1, 2 行的代码保证了头尾两个元素是有序的。第 5 行代码排序完成后，左侧在 $A$ 中最大的 ${\displaystyle \frac{n}{3}}$ 个元素将会转移到中间。第 6 行代码执行前，可以知道最大的 ${\displaystyle \frac{n}{3}}$ 元素要么在中间，要么在右侧。运行完成后，最大的 ${\displaystyle \frac{n}{3}}$ 个元素都在右侧且有序，此时最小的 ${\displaystyle \frac{2n}{3}}$ 个元素均在左侧或中间。执行完成第 7 行代码后，左侧和中间共同保持有序，它们和右侧元素同样保持有序。

此时，算法 STOOGE-SORT 使得序列 $A[p:r]$ 有序。

b

假设算法 STOOGE-SORT 的运行时间为 $T(n)$，那么根据第 5, 6, 7 行的递归，可以发现产生了 $3$ 个大小为 ${\displaystyle \frac{2}{3}}n$ 的子问题，并且每次调用所需要花费的其它操作时间为 $\mathrm{\Theta }(1)$。因此可以写出递推式：$T(n)=3T(2n/3)+\mathrm{\Theta }(1)$。

考虑使用主定理，代入得到 $a=3,b={\displaystyle \frac{3}{2}},f(n)=\mathrm{\Theta }(1),{\log }_{b}a\approx 2.71$。

那么使用第一个条件，可以得到 $T(n)=\mathrm{\Theta }(n^{{\log }_{3/2}3})\approx \mathrm{\Theta }(n^{2.71})$。

c

不能，因为算法 STOOGE-SORT 的最坏时间复杂度比以上所述所有算法的最坏时间复杂度都要糟糕。

7-5

a

考虑使用归纳法进行说明。

可以发现，对于长度为 $2$ 及以下的数组，它们可以正确的被排序。

当长度 $n=p-r+1>2$ 时，考虑进行划分。每一次划分完成后，支点 $q$ 已经到达了正确的已排序位置。并且递归排序数组 $A[p:q]$ 中的部分。根据上面的假设，数组 $A[p:q]$ 最终已经正确排序，并且 $A[p:q]$ 是数组中最小的 $q-p+1$ 个数。在下一次迭代得到新的划分 $q^{\prime }$ 时，支点 $A[q^{\prime }]$ 已经到达了正确的位置，最终正确地递归排序 $A[q+1:q^{\prime }-1]$ 中的数…… 因此循环结束后，整个数组将被正确地排序。

b

当整个数组是已排序的时候，递归的深度可以达到 $\mathrm{\Theta }(n)$。每次划分，数组右侧将会没有元素，而左侧却有 $n-1$ 个。

c

每一次递归调用，参数 $r,p$ 将会满足 $r-p+1$ 的值减少到原来至多一半，因此递归调用的最大深度为 $\mathrm{\Theta }(\lg n)$。可以发现，这份代码总体结构并没有改变，仍然保持着 $O(n\lg n)$ 的运行时间。

TRE-QUICKSORT(A, p, r)
  while p < r
  // Partition and then sort the low side.
    q = PARTITION(A, p, r)
    if q <= ⌊(p + r) / 2⌋
      TRE-QUICKSORT(A, p, q – 1)
      p = q + 1
    else
      TRE-QUICKSORT(A, q + 1, r)
      r = q - 1

7-6

a

假设这个数组的 $n$ 个元素都不相同，随机选取 $3$ 个数，那么有 ${\displaystyle (\genfrac{}{}{0ex}{}{n}{3})}$ 种选法。其中，第 $i$ 小的数成为最终的支点的支点的选法有 $(i-1)\cdot (n-i)$ 种，因为比 $i$ 小的数有 $i-1$ 种选法，比 $i$ 大的数有 $n-i$ 种选法。因此，有

$$p_i={\displaystyle \frac{6(i-1)(n-i)}{n(n-1)(n-2)}}$$

b

按照这个算法，序列 $A$ 的中位数被选上的概率增加了 $p_{\lfloor (n+1)/2\rfloor }-{\displaystyle \frac{1}{n}}$，也就是：

$${\displaystyle \frac{6(\lfloor (n+1)/2\rfloor -1)(n-\lfloor (n+1)/2\rfloor )}{n(n-1)(n-2)}}-{\displaystyle \frac{1}{n}}$$

尝试计算极限 ${\displaystyle \underset{n\to +\mathrm{\infty }}{lim}{\displaystyle \frac{p_{\lfloor (n+1)/2\rfloor }}{1/n}}}$，有

$\begin{array}{rl}\underset{n\to +\mathrm{\infty }}{lim}{\displaystyle \frac{p_{\lfloor (n+1)/2\rfloor }}{1/n}}& =\underset{n\to +\mathrm{\infty }}{lim}{\displaystyle \frac{6(\lfloor (n+1)/2\rfloor -1)(n-\lfloor (n+1)/2\rfloor )}{(n-1)(n-2)}}\\ & ={\displaystyle \frac{6\cdot 1/2\cdot 1/2}{1\cdot 1}}\\ & ={\displaystyle \frac{3}{2}}\end{array}$

c

令 ${\displaystyle s_i=\sum _{j=1}^i{p}_j}$，那么可以得到 $s_i={\displaystyle \frac{i(i-1)(3n-2i-2)}{n(n-1)(n-2)}}$

那么最终结果为 $s_{2n/3}-s_{n/3-1}={\displaystyle \frac{13n^2+9n-90}{27(n-1)(n-2)}}$。

可以得到 ${\displaystyle \underset{n\to +\mathrm{\infty }}{lim}\sum _{i=n/3}^{2n/3}{p}_i=\underset{n\to +\mathrm{\infty }}{lim}{s}_{2n/3}-s_{n/3-1}={\displaystyle \frac{13}{27}}}$。

d

由于最完美的快速排序算法仍然会有 $\mathrm{\Omega }(n\lg n)$ 的下界。这里介绍的划分算法不如最完美的划分算法优秀，偶尔会引入比较坏的情况，因此仍然会有 $\mathrm{\Omega }(n\lg n)$ 的下界。

7-7

本题的思想参考了题目 7-2。假设区间 $I$ 是一部分区间的交集，那么将包含区间 $I$ 的所有区间放数组 $A$ 中间（因为这一些区间全部可以赋予 $I$ 中的同一个数），右端点在 $I$ 左边的区间放在数组 $A$ 左侧，左端点在 $I$ 右侧的区间放在数组 $A$ 右侧，由此递归地排序。

a

// 判断区间A和B是否相交。
IS-INTERSECT(A, B)
  return max{A.l, B.l} <= min{A.r, B.r}

// 区间A和B之交。
INTERSECT(A, B)
  return (max{A.l, B.l}, min{A.r, B.r})

// 这个划分方案将区间划分成三部分：A[p : q - 1], A[q : t], A[t + 1 : r]。其中$A[q : t]$中的所有数全都可以赋值同一个数。
PARTION-INTERVAL(A, p, r)
  i = RANDOM(p, r)
  exchange A[i] with A[p]
  I = A[p]
  i = k = p
  j = r
  while i <= j
    if IS-INTERSECT(I, A[i])
      I = INTERSECT(I, A[i])
      i += 1
    else if A[i].b < I.a
      exchange A[i] and A[k]
      i += 1
      k += 1
    else
      exchange A[i] and A[j]
      j -= 1
  return k, i - 1


QUICKSORT-INTERVAL(A, p, r)
  if p < r
    (q, t) = PARTION-INTERVAL(A, p, r)
    QUICKSORT-INTERVAL(A, p, q - 1)
    QUICKSORT-INTERVAL(A, t + 1, r)

b

如果这些区间是尽可能的重叠，那么它们将会很容易被算法 PARTION-INTERVAL 求出它们的交集 $I$。最终这些区间都被放在了中间，达到了递归终点。算法 QUICKSORT-INTERVAL 将会忽略掉这些已经安排好的区间，如果足够重叠，忽略的区间数足够多，那么就有可能全部忽略完，达到 $\mathrm{\Theta }(n)$ 的时间复杂度。

算法 QUICKSORT-INTERVAL 最终递归求解的是自问 $A[p:q-1],A[t+1:r]$，这两个子问题并不重叠。在最坏情况下，这些区间互相不相交，此时这个算法相当于一般的 RANDOMIZED-QUICKSORT 算法，其时间复杂度为 $\mathrm{\Theta }(n\lg n)$。在一般情况下，这个算法的行为和 RANDOMIZED-QUICKSORT 相同，其时间复杂度为 $\mathrm{\Theta }(n\lg n)$。