算法导论2 Problems 答案

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

2-1

a

插入排序的时间复杂度为\(\Theta(k^2)\)，这个长度为\(n\)的数组中，有\(\dfrac{n}{k}\)个长度为\(k\)的数组。因此插入排序部分的时间复杂度为\(\Theta(k^2)\cdot \dfrac{n}{k}=\Theta(nk)\)。

b

先两两将长度为\(k\)的数组合并成长度为\(2k\)的，再两两将每个\(2k\)的数组合并成\(4k\)的……可以发现这个合并过程是一颗树，整棵树的高度是\(\Theta\left(\lg \dfrac{n}{k}\right)\)。并且，在每一层的合并过程中，整个数组中的所有数恰好都被遍历了一次，花费的时间复杂度总和为\(\Theta(n)\)。因此，最坏情况下合并这\(k\)个数组的时间复杂度为\(\Theta\left(n\cdot \lg \dfrac{n}{k}\right)\)。

c

修改后的归并排序算法为\(\Theta\left(nk + n \lg\dfrac{n}{k}\right)\)，也就是\(\Theta(nk+n\lg n-n\lg k)\)。继续进行如下变换：

\(\begin{aligned} \Theta\left(nk + n \lg\dfrac{n}{k}\right)&=\Theta(nk+n\lg n-n\lg k)\\ &=\Theta(n(k-\lg k)+n\lg n)\\ &=\Theta(nk+n\lg n) \end{aligned}\)

不难发现\(\Theta(k-\lg k)=\Theta(k)\)。

按照上面的式子不难看出，只有当\(k=\Theta(\lg n)\)时，改进后的归并排序算法才能够达到\(\Theta(n\lg n)\)。

d

根据机器性能多次检验后，\(k\)将在\(\Theta(\lg n)\)附近的值中选择。

2-2

a

还需要证明\(A'\)是\(A\)的一个置换（也就是说，\(A'\)的元素都来自于\(A\)）。

b

循环不变量：\(A[j]\)是数组\(A[j:n]\)中的最小值。

初始化：一开始只有一个元素\(A[n]\)，一个元素的数组的最小值肯定是它自身。

保持：在迭代轮次\(j\)前，\(A[j]\)是数组\(A[j:n]\)的最小值。如果\(A[j-1]\le A[j]\)，那么\(A[j-1]\)是数组\(A[j-1:n]\)的最小值；否则，\(A[j]<A[j-1]\)，交换\(A[j]\)和\(A[j-1]\)后，\(A[j-1]\)就变成了数组\(A[j-1:n]\)的最小值。

终止：当\(j=i\)时循环终止。根据循环不变量，\(A[i]\)就是数组\(A[i:n]\)的最小值。

c

循环不变量：数组\(A[1:i-1]\)是由数组的前\(i-1\)小的元素升序排列。

初始化：一开始数组是空的，因此是有序的。

保持：在第\(i\)次循环前，数组\(A[1:i-1]\)是前\(i-1\)小的元素升序排列。根据内循环的循环不变量，第\(i\)次循环完成后，\(A[i]\)是数组\(A[i:n]\)的最小值，那么\(A[i]\)是数组中第\(i\)小的元素。最终，数组\(A[1:i]\)是前\(i\)小的元素升序排列。

终止：最终\(i=n+1\)，算法终止。根据循环不变量，此时数组\(A[1:n]\)是由数组的前\(n\)小的元素升序排列。

d

可以发现，在第\(i\)次迭代中，内循环总是进行了\(n-i\)次。最终外循环结束后，总共的运行时间为\(\Theta(n^2)\)（无论是平均情况还是最坏情况），这与插入排序最坏情况相同。

2-3

a

\[\Theta(n)\]

b

1
2
3
4
5
6
7
8
HORNER-NAIVE(A, n, x)
  p = 0
  for i = 0 to n
    pow_x = 1
    for j = 1 to i
      pow_x = pow_x * x
    p = p + pow_x * A[i]
  return p

在第\(i\)次迭代中，内循环迭代了\(i\)次，因此整个算法的运行时间为\(\Theta(n^2)\)，相比原算法慢了很多。

c

令\(\displaystyle{p(i)=\sum_{k=0}^{n-(i+1)} A[k+i+1]\cdot x^k}\)

初始化：容易发现\(p(n)=0\)，因为此时求和式的上限值为\(-1\)，与定义相同。

保持：在第\(i\)次循环前，\(p\)的值为\(p(i)\)。那么在\(p(i)\)次循环完成后，数值已经变成\(p(i)\cdot x+A[i]\)。进行以下恒等变换：

\(\begin{aligned} \left(x\cdot \sum_{k=0}^{n-(i+1)} A[k+i+1]\cdot x^k\right) + A[i]&=\left( \sum_{k=0}^{n-(i+1)} A[k+i+1]\cdot x^{k+1}\right) + A[i]\\ &=\left( \sum_{k=1}^{n-i} A[k+i]\cdot x^k\right) +A[i]\cdot x^0\\ &=\sum_{k=0}^{n-i} A[k+i]\cdot x^k\\ &=\sum_{k=0}^{n-((i-1)+1)} A[k+(i-1)+1]\cdot x^k\\ &=p(i-1) \end{aligned}\)

那么可以发现，完成一次迭代后，\(p\)的值从\(p(i)\)转换成\(p(i-1)\)，循环不变量相同。

终止：当\(i=-1\)时，循环终止。那么可以发现\(\displaystyle{p(-1)=\sum_{k=0}^{n} A[k]\cdot x^k}\)，与最终目标所求值一致，因此算法时正确的。

2-4

a

\([(1,5),(2,5),(3,4),(3,5),(4,5)]\)

b

置换\(\langle n,n-1,n-2,\dots,1\rangle\)能够得到最多的逆序数（每一对都包含），其值为\(n-1+n-2+\dots + 0=\dfrac{n(n-1)}{2}\)。

c

以下是插入排序算法的代码：

1
2
3
4
5
6
7
8
INSERTION-SORT(A, n)
  for i = 2 to n
    key = A[i]
    j = i – 1
    while j > 0 and A[j] > key
      A[j + 1] = A[j]
      j = j – 1
    A[j + 1] = key

假设\(f(i)\)的含义是：对于下标元素\(A[i]\)，满足\(j< i, A[j]>A[i]\)的下标\(j\)的数量。数组\(A\)的逆序数就为\(\sum_{i=1}^n f(i)\)。

那么，程序的运行时间和值\(\sum_{i=1}^n f(i)\)线性相关。对于第\(i\)次循环，while循环体内做的事情恰好是将比所有比\(A[i]\)大的数向右边移动。最终整个程序的运行时间和这个逆序数线性相关。

d

程序CAL-INVERSION(A, p, r)：计算数组\(A[p:r]\)中的逆序数，并且对\(A[p:r]\)进行归并排序。

1
2
3
4
5
6
7
8
CAL-INVERSION(A, p, r)
  if p >= r
    return 0
  q = floor((p + r) / 2)
  left_inversion = CAL-INVERSION(A, p, q)
  right_inversion = CAL-INVERSION(A, q + 1, q)
  new_inversion = MERGE(A, p, q)
  return left_inversion + right_inversion + new_inversion

程序MERGE2(A, p, q, r)：数组\(A[p:q],A[q+1:r]\)已经有序。将这两个有序数组合并时产生的逆序数。这个程序由程序MERGE(A, p, q, r)修改而来。

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
MERGE2(A, p, q, r)
  inversion_count = 0
  nL = q – p + 1 // length of A[p : q]
  nR = r – q // length of A[q + 1 : r]
  let L[0 : nL – 1] and R[0 : nR – 1] be new arrays
  for i = 0 to nL – 1 // copy A[p : q] into L[0 : nL – 1]
    L[i] = A[p + i]
  for j = 0 to nR – 1 // copy A[q + 1 : r] into R[0 : nR – 1]
    R[j] = A[q + j + 1]
  i = 0 // i indexes the smallest remaining element in L
  j = 0 // j indexes the smallest remaining element in R
  k = p // k indexes the location in A to fill
  // As long as each of the arrays L and R contains an unmerged element,
  // copy the smallest unmerged element back into A[p : r].
  while i < nL and j < nR
    if L[i] ≤ R[j]
      A[k] = L[i]
      i = i + 1
    else A[k] = R[j]
      inversion_count = inversion_count + nL - i
      // 这说明L中还有nL-i个数大于R[j]，这些数对R[j]贡献了逆序数。
      j = j + 1
    k = k + 1
  // Having gone through one of L and R entirely, copy the
  // remainder of the other to the end of A[p : r].
  while i < nL
    A[k] = L[i]
    i = i + 1
    k = k + 1
  while j < nR
    A[k] = R[j]
    j = j + 1
    k = k + 1
  return inversion_count