算法导论2.3 Exercises 答案

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

2.3-1

\(\begin{aligned} &[3,41,52,26,38,57,9,49]\\ &[3,41,52,26]\quad[38,57,9,49]\\ &[3,41]\quad[52,26]\quad[38,57]\quad[9,49]\\ &[3]\quad[41]\quad[52]\quad[26]\quad[38]\quad[57]\quad[9]\quad[49]\\ &[3,41]\quad[26,52]\quad[38,57]\quad[9,49]\\ &[3,26,41,52]\quad[9,38,49,57]\\ &[3,9,26,38,41,49,52,57] \end{aligned}\)

2.3-2

如果\(r-p+1=1\)，说明恰好触发了\(r=p\)的条件。MERGE-SORT算法终止。

假设\(n>2\)，一开始调用MERGE-SORT(A,1,n)就已经意味着\(1=p< r=n\)。

令\(q=\left\lfloor\dfrac{p+r}{2}\right\rfloor\)，由于\(r>p\)，因此必定保证\(p\le q\)。

考虑\(q+1\)和\(r\)的关系：如果\(r-p+1\le 2\)，那么\(q+1=r\)。如果\(r-p+1>2\)，那么\(q+1< r\)。因此\(q+1\le r\)总能保证。

最终，只要调用时已经保证\(p< r\)，那么接下来的两次调用参数总满足\(p\le q,q+1\le r\)。假设新调用的参数为\(p',r'\)，那么也就是只会满足\(p'\le r'\)，不会出现\(p'>r'\)的情况。

2.3-3

循环不变量：数组\(L[i:n_L-1]\)和\(R[j:n_R-1]\)保持有序。

初始化：一开始数组\(A[p:r]\)是空的，视为已经排序。

保持：在第\(i+j\)次迭代前，由于数组\(L,R\)已经排序，因此\(L[i]\)是数组\(L[i:n_L-1]\)的最小值，\(R[j]\)是数组\(R[j:n_R-1]\)的最小值。当前的\(k\)值要么满足\(k=p\)，要么满足\(A[k-1]\le \min(L[i],R[j])\)。因此取出\(L[i]\)和\(R[j]\)中的最小值，并复制给\(A[k]\)。不失一般性，假设赋给\(A[k]\)的值是\(L[i]\)，那么迭代完成后，\(L[i+1]\)仍然是数组\(L[i+1:n_R-1]\)的最小值。由于\(i<i+1\)，因此\(A[k]\le L[i+1]\)；由于选择的是\(L[i]\)，因此\(A[k]\le R[j]\)，那么\(A[k]\le \min(L[i+1],R[j])\)依旧保持着，直到第12-18行的代码的循环结束。

终止：终止条件要么是\(i=n_L\)，要么是\(j=n_R\)。不失一般性，假设此时已经满足\(i=n_L\)，那么说明\(j< n_R\)。由于\(L[n_L-1]\)先被选择，因此满足\(A[k-1]=L[n_L-1]\le R[j]\)。由于数组\(R\)是有序的。因此$L[n_L-1]R[j]R[j-1]R[n_R-1] $保持有序，直接通过循环将这一段剩下的序列复制到重点即可。

2.3-4

令\(f(m)=T(2^m)\)，那么代入递推式\(T(n)\)，

\(f(m)= \left \{\begin{aligned} &2 & & \text{if}\quad m=1 \\ &2f(m-1)+2^m & & \text{if}\quad m>1 \\ \end{aligned}\right.\)

第二行递推式可以改写成\(\dfrac{f(m)}{2^m}=\dfrac{f(m-1)}{2^{m-1}}+1\)，可以发现数列\(\dfrac{f(m)}{2^m}\)是首项、公差均为\(1\)的等差数列，因此有\(\dfrac{f(m)}{2^m}=m\)，也就是说\(f(m)=m\cdot 2^m\)。

最终回代\(f(m)=T(2^m)\)，得到\(T(n)=n\cdot \lg n\)。

2.3-5

1
2
3
4
5
6
7
8
9
10
INSERTION-SORT(A, n)
  if n == 1:
    return
  INSERTION-SORT(A, n - 1)
  key = A[n]
  j = n – 1
  while j > 0 and A[j] < key
    A[j + 1] = A[j]
    j = j – 1
    A[j + 1] = key

在最坏情况下，while循环体最多会执行\(n\)次，因此可以写出如下\(T(n)\)的递推式：

\(T(n)= \left \{\begin{aligned} &1 & & \text{if}\quad n=1 \\ &T(n-1)+n & & \text{if}\quad n>1 \\ \end{aligned}\right.\)

2.3-6

1
2
3
4
5
6
7
8
9
10
11
12
13
// 数组A长度为n，寻找值x。
BINARY-SEARCH(A, n, x)
  l = 1
  r = n
  while l <= r
    mid = floor((l + r) / 2)
    if A[mid] == x
      return mid
    else if A[mid] < x
      l = mid + 1
    else
      r = mid - 1
  return NIL

在最差的情况下，循环不会从return mid中结束。因此，在每一次迭代过程中，\(r-l+1\)的大小将会被缩减一半。不难写出递推式\(T(n)=T(n/2)+\Theta(1)\)，从而得到\(T(n)=\Theta(\lg n)\)

2.3-7

使用二分搜索并不能优化插入排序。二分搜索只能以\(\Theta(\lg n)\)的时间复杂度定位到元素应该插入到哪个位置，但是将比当前key大的所有数往后移动一个下标，依然需要\(\Theta(n)\)的时间。

2.3-8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 输入集合S，集合的大小n，题中所求x。
// 返回1表示符合条件，否则返回0.
SEARCH-SUM-X(S, n, x)
  A = to_array(S)
  MERGE-SORT(A, 1, n)
  l = 1
  r = n
  while l < r
    if A[l] + A[r] == x
      return 1
    else if A[l] + A[r] > x
      r = r - 1
    else
      l = l + 1
  return 0