算法导论9.3 Exercises 答案

发表于 2023-01-17 更新于 2023-09-30 分类于算法导论阅读次数：本文字数： 3.2k 阅读时长 ≈ 3 分钟

9.3-1

前11行代码，无非就是将所有为\(5\)的常量转化成\(7\)。这一段的代码运行时间仍然为\(\Theta(n)\)。

第12-13行代码对每组\(7\)个元素进行原地排序。由于每组内部元素数量相同，一共有\(\Theta(n)\)组，这一段的运行时间仍然为\(\Theta(n)\)。

第16行对中间的一组再进行一次调用，产生了\(T(n/7)\)的开销。

第17行对数组进行了一次划分，这一段的运行时间仍然为\(\Theta(n)\)。

总而言之，上面这部分算法内部开销的时间复杂度为\(\Theta(n)\)。

第20-24行递归进入所划分的区间。按照这种划分方法，可以知道，第16行中的\(x\)至少有\(\dfrac{4\cdot n}{2\cdot 7}=\dfrac{2}{7}n\)个数比它大，至少有\(\dfrac{2}{7}n\)个数比它小。因此每次进行下一次递归时，至多可以去除\(\dfrac{2}{7}n\)个数。假设\(T(n)\)为对\(n\)个元素进行选择的运行时间，那么有

\[T(n)\le T(n/7)+T(5n/7)+\Theta(n)\]

使用代入法，假设对于足够大的所有\(n,T(n)\le cn\)都成立。那么有

\(\begin{aligned} T(n)&\le T(n/7)+T(5n/7)+\Theta(n)\\ &\le cn/7+5cn/7+\Theta(n)\\ &=cn-cn/7+\Theta(n)\\ &\le cn &\qquad(A) \end{aligned}\)

其中，步骤\((A)\)假设了\(c\)足够大，以至于\(cn/7\)的增长速度超过\(\Theta(n)\)。

因此有\(T(n)=O(n)\)。

由于第17行对数组进行了一次\(\Theta(n)\)的划分，因此说明\(T(n)=\Omega(n)\)。

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

9.3-2

在这个时候，我们考虑不处理最后\(A[5g+1:n]\)这一部分元素，留给下一次递归一并进行处理。

第12-13行代码对每组\(5\)个元素进行原地排序。由于每组内部元素数量相同，一共有\(\Theta(n)\)组，这一段的运行时间仍然为\(\Theta(n)\)。

第16行对中间的一组再进行一次调用，产生了\(T(n/5)\)的开销。

第17行对数组进行了一次划分，这一段的运行时间仍然为\(\Theta(n)\)。

总而言之，上面这部分算法内部开销的时间复杂度为\(\Theta(n)\)。

第20-24行递归进入所划分的区间。按照这种划分方法，可以知道，第16行中的\(x\)至少有\(\dfrac{3}{10}n\)个数比它大，至少有\(\dfrac{3}{10}n\)个数比它小。因此每次进行下一次递归时，至多可以去除\(3n/10\)个数。假设\(T(n)\)为对\(n\)个元素进行选择的运行时间，那么考虑将不属于群中的元素交给下一次递归处理，那么有

\(T(n)\le T(7n/10+(n\bmod 5)) + \Theta(n) \le T(7n/10+4)+\Theta(n)\)

按照第四章的内容，递推式中的常数并不影响其最终的渐进增长表达。因此假设\(T'(n) \le T'(7n/10)+\Theta(n)\)，那么\(T(n)=\Theta(T'(n))\)。

参考题目9.3-1类似的推理，有\(T'(n)=O(n)\)，因此\(T(n)=O(n)\)。

第17行对数组进行了一次\(\Theta(n)\)的划分，说明\(T(n)=\Omega(n)\)。

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

9.3-3

将快速排序中调用子程序RANDOMIZED-PARTITION的那一行改为使用SELECT查找中位数。

使用算法SELECT找到中位数后，两部分将会被划分尽量均等的两部分。按照上面的结论，假设对\(n\)个数进行快速排序的时间复杂度为\(T(n)\)，那么有

\[T(n)=2T(n/2)+O(n)\]

因此通过主定理不难得知，\(T(n)=O(n\lg n)\)。

\(\star\) 9.3-4

令图\(G=(V,E)\)表示通过这个算法比较产生的一个有向图。其中\(V\)是\(n\)个顶点，顶点\(v_i\in V\)表示数组\(A\)中的第\(i\)个元素。

在调用这个基于比较的算法求第\(i\)小的数的过程中，额外增加如下过程：如果\(A[x]\ge A[y]\)，那么在\(E\)中增加一条边\((v_x,v_y)\)。

为了知道第\(i\)小的元素是哪一个，它必定和其它所有数有着间接的关系。因此图\(G\)的基图是一个连通图。

那么，对于任意一个\(j\)，如果从\(v_j\)到\(v_i\)存在一条路径，那么找到了一个超过\(A[i]\)的数\(A[j]\)；如果从\(v_i\)到\(v_j\)存在一条路径，那么找到了一个小于\(A[i]\)的数\(A[j]\)。

自此，不需要比较就能找到其余\(i-1\)个小数和\(n-i\)个大数。

9.3-5

由算法GET-MEDIAN详细描述整个过程。

GET-MEDIAN(a1, a2, a3, a4, a5)
  // 1
  if a1 > a2
    exchange a1 with a2
  // 2
  if a3 > a4
    exchange a3 with a4
  // 3
  if a1 > a3
    exchange a1 with a3
    exchange a2 with a4
  // 此时已经保证a1 <= a3 <= a4, a1 <= a2
  // 4
  if a2 <= a5
    // 此时已经保证a1 <= a3 <= a4, a1 <= a2 <= a5
    // 5.1
    if a2 > a3
      exchange a2 with a3
      exchange a4 with a5
    // 此时已经保证a1 <= a2 <= a3 <= a4, a2 <= a5
    // 6.1
    if a3 <= a5
      // 此时有a1 <= a2 <= a3 <= a4 & a5，那么a3是中位数。
      return a3
    else
      // 此时有a1 <= a2 <= a5 < a3 <= a4，那么a5是中位数。
      return a5
  else
    // 此时已经保证a1 <= a3 <= a4, a1 <= a2, a5 < a2
    // 5.2
    if a3 <= a5
      // 此时已经保证a1 <= a3 <= a5 < a2, a3 <= a4
      // 6.2
      if a4 <= a5
        // 此时有a1 <= a3 <= a4 <= a5 < a2，那么a4是中位数。
        return a4
      else
        // 此时有a1 <= a3 <= a5 <= a2 & a4，那么a5是中位数。
        return a5
    else
      // 此时已经保证 a1 <= a3 <= a4, a1 <= a2, a5 < a2 & a3
      // 6.3
      if a2 <= a3
        // 此时有a1 & a5 < a2 <= a3 <= a4，那么a2是中位数。
        return a2
      else
        // 此时有a1 & a5 <= a3 <= a2 & a4，那么a3是中位数。
        return a3

9.3-6

由算法SELECT2给出整个过程，基本思想是分治。如果查找的\(i\)比中位数的排名小，那么就在左边部分继续查找；如果查找的\(i\)恰好和中位数排名相等，那么返回这个中位数；如果查找的\(i\)比中位数的排名大，那么就在右边部分继续查找。

// 子程序MEDIAN(A, p, r)表示返回序列A[p : r]的中位数下标q，并且已经将整个数组划分得A[p : q - 1]都比A[q]小，A[q + 1 : r]都比A[q]大。
SELECT2(A, p, r, i)
  q = MEDIAN(A, p, r)
  k = q - p + 1
  if i == k
    return A[q]
  else if i < k
    return SELECT2(A, p, q - 1, i)
  else
    return SELECT2(A, q + 1, r, i - k)

按照题目要求，算法MEDIAN的运行时间为\(\Theta(n)\)，那么程序SELECT2的运行时间\(T(n)\)满足\(T(n)=T(n/2)+\Theta(n)\)。根据主定理，\(T(n)=\Theta(n)\)，因此这个算法符合题意。

9.3-7

这个管道的铺设纵坐标是所有油田纵坐标的中位数，直接调用SELECT(Y, 1, n, ⌈n/2⌉)即可在\(O(n)\)的时间下求解。

证明：假设目前的某个候选解为\(y\)，在它上面的油田有\(a\)个，在它下面的油田有\(b\)个。如果\(a>b\)，那么将候选解\(y\)增加\(1\)，那么管道总长度将会减少\(a-b\)；类似的，如果\(a< b\)，那么将\(y\)减少\(1\)，那么管道总长度减少\(b-a\)。

因此为了保证管道总长度最小，\(a\)和\(b\)的值应该尽量接近，此时取得的解恰好为油田纵坐标的中位数。

9.3-8

由算法GET-QUANTILES给出整个过程，基本思想仍然是分治。可以发现，这个递归至多只会进行\(\Theta(\lg k)\)层。并且在同一层中，划分的区间总是不相交的。因此在每一层中，第6行代码调用程序SELECT的总时间为\(O(n)\)。因此整个程序的时间复杂度为\(O(n\lg k)\)。


// 第kl~kr个分位数在数组A[al : ar]中，并且将求出来的分位数存放在B中。
GET-QUANTILES(A, al, ar, kl, kr, B, k)
  if al > ar or kl > kr
    return
  n = ar - al + 1
  kp = ⌊(kl + kr) / 2⌋
  ap = ⌊kp * n / k⌋
  x = SELECT(A, al, ar, ap)
  B[kp] = x
  GET-QUANTILES(A, al, ap - 1, kl, kp - 1, B, k)
  GET-QUANTILES(A, ap + 1, ar, kp + 1, kr, B, k)

K-QUANTILES(A, n, k) 
  let B[1 : k - 1] be new array
  GET-QUANTILES(A, 1, n, 1, k - 1, B, k)
  return B

9.3-9

由算法K-CLOSET-MEDIAN给出整个过程。第一次SELECT的调用是为了找出中位数，后面的两次调用是为了找出这连续的\(k\)个数的左右边界。注意当\(k\)为偶数时，还需要判断第\(\lceil n\rceil-k/2\)小的数和第\(\lceil n\rceil+k/2\)小的数中，哪个更加接近中位数。

由于整个过程只调用了\(3\)次SELECT算法，因此算法K-CLOSET-MEDIAN的时间复杂度为\(O(n)\)。

K-CLOSET-MEDIAN(S, n, k)
  m = SELECT(Y, 1, n, ⌈n/2⌉)
  if k % 2 == 1
    x = SELECT(Y, 1, n, ⌈n/2⌉-(k-1)/2)
    y = SELECT(Y, 1, n, ⌈n/2⌉+(k-1)/2)
    return S[⌈n/2⌉-(k-1)/2 : ⌈n/2⌉+(k-1)/2]
  else
    x = SELECT(S, 1, n, ⌈n/2⌉-k/2)
    y = SELECT(S, 1, n, ⌈n/2⌉+k/2)
    if |x - m| <= |y - m|
      return S[⌈n/2⌉-k/2 : ⌈n/2⌉+k/2-1]
    else
      return S[⌈n/2⌉-k/2+1 : ⌈n/2⌉+k/2]

9.3-10

题目本质上是找出这\(2n\)个数中第\(n\)小的数。整个过程由算法SELECT3给出。

算法SELECT3的每一次调用将会淘汰一个数组中\(\lfloor k/2\rfloor\)个较小数，使得所求中位数的排名上升一半。由于一共需要淘汰\(n\)个数，因此整个算法的时间复杂度为\(O(\lg n)\)。

// 找出数组A[i : n], B[j : n]中的第k小数。
SELECT3(n, A, i, B, j, k) 
  if i > n
    return B[j + k - 1]
  else if j > n
    return A[j + k - 1]
  else if k == 1
    return min{A[i], B[j]}
  if i + ⌊k/2⌋ - 1 <= n
    midl = A[i + ⌊k/2⌋ - 1]
  else
    midl = +∞
  if j + ⌊k/2⌋ - 1 <= n
    midr = B[i + ⌊k/2⌋ - 1]
  else
    midr = +∞
  if midl < midr
    return SELECT3(n, A, i + ⌊k/2⌋, B, j, k - ⌊k/2⌋)
  else
    return SELECT3(n, A, i, B, j + ⌊k/2⌋, k - ⌊k/2⌋)
 
MEDIAN3(A, B, n)
  return SELECT3(n, A, 1, B, 1, n)