算法导论7 Problems 答案

发表于 更新于 分类于 阅读次数： 本文字数： 7.4k 阅读时长 ≈ 7 分钟

7-1

a

可以知道，此时支点值\(x\)为\(13\)。

\(\begin{array}{|c|c|c|} \hline &i&j\\ \hline \langle 13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21\rangle \\ \hline \langle \underline{6}, 19, 9, 5, 12, 8, 7, 4, 11, 2, \underline{13}, 21\rangle &1&13\\ \hline \langle 6, \underline{2}, 9, 5, 12, 8, 7, 4, 11, \underline{19}, 13, 21\rangle & 2 & 10\\ \hline \langle 6, 2, 9, 5, 12, 8, 7, 4, \underline{11}, 19, 13, 21\rangle &10&9\\ \hline \end{array}\)

b

当数组中所有元素都相等时，HOARE-PARTITION将会返回\(\left\lfloor\dfrac{p+r}{2}\right\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

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

f

1
2
3
4
5
6
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)+\Theta(n)=\Theta(n^2)\)。

b

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 返回的两个下标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'的时间复杂度为\(\Theta(r-p)\)。

c

1
2
3
4
5
6
7
8
9
10
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\)排序后的结果为\(\langle z_1,z_2,\dots,z_n\rangle\)，满足\(z_1\le z_2\le \dots\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 \dfrac{2}{j-i+1}\)，而不再是等于。

因此，有

\(\begin{aligned} E[X]&= \sum_{i=1}^{n-1}\sum_{j=i+1}^n \dfrac{2}{j-i+1}\\ &\ge \sum_{i=1}^{n-1}\sum_{k=1}^{n-i} \dfrac{2}{k+1}\\ &\ge \sum_{i=1}^{n-1}\sum_{k=1}^{n-i} \dfrac{2}{2k}&\qquad(A)\\ &=\sum_{i=1}^{n-1} \Omega(\lg n)\\ &=\Omega(n\lg n) \end{aligned}\)

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

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

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

因此，最终有\(T(n)=\Theta(n\lg n)\)。

7-3

a

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

b

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

\(\begin{aligned} E[T(n)]&=E\left[\sum_{q=1}^n X_q\cdot (T(q-1)+T(n-q))\right] + \Theta(n)\\ &=E\left[\sum_{q=1}^n X_q\cdot (T(q-1)+T(n-q)+ \Theta(n))\right] \end{aligned}\)

c

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

\(\begin{aligned} E[T(n)]&=E\left[\sum_{q=1}^n X_q\cdot (T(q-1)+T(n-q)+ \Theta(n))\right]\\ &=E\left[\sum_{q=1}^n X_q\cdot (T(q-1)+T(n-q))\right]+ \Theta(n)\\ &=\sum_{q=1}^n (E[X_q]\cdot (E[T(q-1)+T(n-q)]))+ \Theta(n)\\ &=\sum_{q=1}^n \left(\dfrac{1}{n}\cdot (E[T(q-1)]+E[T(n-q)])\right)+ \Theta(n)\\ &=\dfrac{2}{n}\sum_{q=1}^{n-1} E[T(q)]+ \Theta(n)\\ \end{aligned}\)

d

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

\(\begin{aligned} \sum_{q=1}^{n-1} q\lg q&\le \int_{1}^{n} x\lg x dx \\ &=\left.\dfrac{1}{2} x^2\lg x-\dfrac{x^2}{4\ln 2}\right|_{1}^n\\ &=\dfrac{n^2}{2} \lg n-\dfrac{n^2}{4\ln 2}+\dfrac{1}{4\ln 2}\\ &\le \dfrac{n^2}{2} \lg n-\dfrac{n^2}{8}&\qquad(n\ge 2) \end{aligned}\)

当\(n=1\)时，可以验证原式仍然成立。因此\(\forall n\ge 1\)，都有\(\displaystyle{\sum_{q=1}^{n-1} q\lg q\le \dfrac{n^2}{2} \lg n-\dfrac{n^2}{8}}\)。

e

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

\(\begin{aligned} E[T(n)]&=\dfrac{2}{n}\sum_{q=1}^{n-1} E[T(q)]+ \Theta(n)\\ &\le c\cdot \dfrac{2}{n}\left(\dfrac{n^2}{2}\lg n-\dfrac{n^2}{8}\right) + \Theta(n)\\ &=cn\lg n-\dfrac{cn}{4}+\Theta(n)\\ &=cn\lg n-\left(\dfrac{cn}{4}-\Theta(n)\right)\\ &\le cn\lg n & \qquad(A) \end{aligned}\)

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

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

7-4

a

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

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

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

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

b

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

考虑使用主定理，代入得到\(a=3,b=\dfrac{3}{2},f(n)=\Theta(1),\log_b a\approx 2.71\)。

那么使用第一个条件，可以得到\(T(n)=\Theta(n^{\log_{3/2} 3})\approx \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'\)时，支点\(A[q']\)已经到达了正确的位置，最终正确地递归排序\(A[q+1:q'-1]\)中的数……因此循环结束后，整个数组将被正确地排序。

b

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

c

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

1
2
3
4
5
6
7
8
9
10
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\)个数，那么有\(\dbinom{n}{3}\)种选法。其中，第\(i\)小的数成为最终的支点的支点的选法有\((i-1)\cdot (n-i)\)种，因为比\(i\)小的数有\(i-1\)种选法，比\(i\)大的数有\(n-i\)种选法。因此，有

\[p_i=\dfrac{6(i-1)(n-i)}{n(n-1)(n-2)}\]

b

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

\[\dfrac{6(\lfloor(n+1)/2\rfloor-1)(n-\lfloor(n+1)/2\rfloor)}{n(n-1)(n-2)}-\dfrac{1}{n}\]

尝试计算极限\(\displaystyle{\lim_{n\rightarrow +\infty} \dfrac{p_{\lfloor(n+1)/2\rfloor}}{1/n}}\)，有

\(\begin{aligned} \lim_{n\rightarrow +\infty} \dfrac{p_{\lfloor(n+1)/2\rfloor}}{1/n} &= \lim_{n\rightarrow +\infty} \dfrac{6(\lfloor(n+1)/2\rfloor-1)(n-\lfloor(n+1)/2\rfloor)}{(n-1)(n-2)} \\&=\dfrac{6\cdot 1/2\cdot 1/2}{1\cdot 1}\\ &=\dfrac{3}{2} \end{aligned}\)

c

令\(\displaystyle{s_i=\sum_{j=1}^i p_j}\)，那么可以得到\(s_i=\dfrac{i(i-1)(3n-2i-2)}{n(n-1)(n-2)}\)

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

可以得到\(\displaystyle{\lim_{n\rightarrow +\infty} \sum_{i=n/3}^{2n/3} p_i=\lim_{n\rightarrow +\infty} s_{2n/3}-s_{n/3-1}=\dfrac{13}{27}}\)。

d

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

7-7

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

a

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

// 判断区间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将会忽略掉这些已经安排好的区间，如果足够重叠，忽略的区间数足够多，那么就有可能全部忽略完，达到\(\Theta(n)\)的时间复杂度。

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