算法导论6 Problems 答案

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

6-1

a

不会。以数组\(\langle1,2,3,4\rangle\)为例，使用BUILD-MAX-HEAP建堆的结果为\(\langle4,1,3,2\rangle\)，使用BUILD-MAX-HEAP'建堆的结果为\(\langle4,3,2,1\rangle\)。

b

当元素\(A\)的顺序是有序时，将达到最坏情况，因为此时新加入的元素都会从叶节点上升到根节点，第\(i\)次加入的元素在第$ i \(层，因此其运行时间\)T(n)$满足：

\(\displaystyle{T(n)=\sum_{k=2}^n \lg k = \lg n! = \Theta(n\lg n)}\)

6-2

a

使用数组来表示\(d\)叉堆的方式如下：

1
2
3
4
5
6
7
// 参数d假设已经存在。
D-PARENT(i)
  return ⌊(i - 2) / d⌋ + 1

// 求下标为i的第j个孩子节点的下标，1 <= j <= d
D-CHILD(i, j)
  return d * (i - 1) + j + 1

正确性：自己的孩子的父亲必定为自身：\(\left\lfloor\dfrac{(d(i-1)+j+1)-2}{d}\right\rfloor+1=i-1+\left\lfloor\dfrac{j-1}{d}\right\rfloor+1=i\)。

b

每个节点的都会有\(d\)个，它的高度将会以\(d\)为底数的速度增长，即\(\Theta(\log_d n)\)。

c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
D-MAX-HEAP-EXTRACT-MAX(A)
  if A.heap-size < 1
    error “heap underflow”
  max = A[1]
  A[1] = A[A.heap-size]
  A.heap-size = A.heap-size – 1
  D-MAX-HEAPIFY(A, 1)
  return max

D-MAX-HEAPIFY(A, i)
  largest = i
  for j = 1 to d
    son = D-CHILD(i, j)
    if son <= A.heap-size and A[son] > A[largest]
      largest = son
  if largest ≠ i
    exchange A[i] with A[largest]
    D-MAX-HEAPIFY(A, largest)

算法D-MAX-HEAP-EXTRACT-MAX没有循环制语句，仅仅第6行调用了子程序D-MAX-HEAPIFY。因此处主要分析算法D-MAX-HEAPIFY的效率。

算法D-MAX-HEAPIFY是个递归的程序，第8行表明每进行一次递归它将会向叶节点移动，因此按照题目6-1-b的结论，这个算法最多递归\(\Theta(\log_d n)\)次。第2行的for循环用于维护最大堆的结构，查找最大的子节点，并且循环结束后将会和父节点交换，其循环的次数为\(d\)。

因此，整个算法的时间复杂度为\(\Theta(d\log_d n)\)。

d

1
2
3
4
5
6
7
8
D-MAX-HEAP-INCREASE-KEY(A, x, k)
  if k < x.key
    error “new key is smaller than current key”
  x.key = k
  find the index i in array A where object x occurs
  while i > 1 and A[PARENT(i)].key < A[i].key
    exchange A[i] with A[PARENT(i)], updating the information that maps priority queue objects to array indices
  i = D-PARENT(i)

算法D-MAX-HEAP-INCREASE-KEY的时间复杂度为\(O(\log_d n)\)，因为while执行的次数不超过整个\(d\)叉堆的高度。

e

1
2
3
4
5
6
7
8
9
D-MAX-HEAP-INSERT(A, x, n)
  if A.heap-size == n
    error “heap overflow”
  A.heap-size = A.heap-size + 1
  k = x.key
  x.key = –∞
  A[A.heap-size] = x
  map x to index heap-size in the array
  D-MAX-HEAP-INCREASE-KEY(A, x, k)

算法D-MAX-HEAP-INSERT没有循环制语句，仅仅第8行调用了子程序D-MAX-HEAP-INCREASE-KEY。因此这个算法的时间复杂度和D-MAX-HEAP-INCREASE-KEY一样，为\(O(\log_d n)\)。

6-3

a

\(\begin{aligned} & 2 && 3 && 4 && 5\\ & 8 && 9 && 12 && 14\\ & 16 && \infty && \infty && \infty\\ & \infty && \infty && \infty && \infty \end{aligned}\)

b

如果\(Y[1,1]=\infty\)，由于\(Y\)矩阵的第\(1\)行是从小到大排序的，那么只能有\(Y[1,2]=Y[1,3]=\dots=Y[1,n]=\infty\)。由于\(Y\)矩阵每列都是从小到大排序的，那么整个矩阵全部元素都为\(\infty\)，因此整个矩阵为空。

类似的，如果\(Y[m,n]<\infty\)，那么由于\(Y\)矩阵的第\(m\)行是从小到大排序的，那么有\(Y[m,1]<\infty,T[m,2]<\infty,\dots,Y[m,n-1]<\infty\)。由于\(Y\)矩阵每列都是从小到大排序的，那么整个矩阵全部元素都不为\(\infty\)，因此整个矩阵为满。

c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
MIN-Y(A, m, n, i, j)
  if j < n and A[i, j + 1] < A[i, j]
    (smallesti, smallestj) = (i, j + 1)
  else
    (smallesti, smallestj) = (i, j)
  if i < m and A[i + 1, j] < A[smallesti, smallestj]
    (smallesti, smallestj) = (i + 1, j)
  if (i, j) != (smallesti, smallestj)
    exchange A[i, j] and A[smallesti, smallestj]
    MIN-Y(A, m, n, smallesti, smallestj)

EXTRACT-MIN-Y(A, m, n)
  min = A[1, 1]
  A[1, 1] = ∞
  MIN-Y(A, m, n, 1, 1)
  return min

算法EXTRACT-MIN-Y没有循环制语句，仅仅第3行调用了子程序MIN-Y。因此处主要分析算法MIN-Y的效率。

算法MIN-Y是个递归的程序，它每调用自身一次后，要么\(i\)增加\(1\)，要么\(j\)增加\(1\)。因此这个程序最多有\(n+m-1\)次递归调用。因此整个程序的时间复杂度为\(O(n+m)\)。

d

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
MIN-Y'(A, m, n, i, j)
  if j > 1 and A[i, j - 1] > A[i, j]
    (largesti, largestj) = (i, j - 1)
  else
    (largesti, largestj) = (i, j)
  if i > 1 and A[i - 1, j] > A[largesti, largestj]
    (largesti, largestj) = (i - 1, j)
  if (i, j) != (largesti, largestj)
    exchange A[i, j] and A[largesti, largestj]
    MIN-Y'(A, m, n, largesti, largestj)

INSERT-Y(A, m, n, x)
  if A[m, n] != ∞
    error “heap overflow”
  A[m, n] = x
  MIN-Y'(A, m, n, m, n)


本题和题目6-3-c非常相似。

算法INSERT-Y没有循环制语句，仅仅第4行调用了子程序MIN-Y'。因此处主要分析算法MIN-Y'的效率。

算法MIN-Y'是个递归的程序，它每调用自身一次后，要么\(i\)减少\(1\)，要么\(j\)减少\(1\)。因此这个程序最多有\(n+m-1\)次递归调用。因此整个程序的时间复杂度为\(O(n+m)\)。

e

1
2
3
4
5
6
7
8
9

// A是一个含有n^2个元素的序列
SORT-BY-Y(A, n)
  lew B[1 : n, 1 : n] be new table with ∞
  for i = 1 to n * n
    INSERT-Y(B, n, n, A[i])
  for i = 1 to n * n
    A[i] = EXTRACT-MIN-Y(A, n, n)
  return A

由于第2, 4行中的循环长度都是\(n^2\)，算法INSERT-Y, EXTRACT-MIN的时间复杂度都是\(O(n)\)，因此算法SORT-BY-Y的时间度为\(O(n^3)\)。

f

1
2
3
4
5
6
7
8
9
10
11
FIND-Y(A, m, n, x)
  i = m
  j = 1
  while i >= 1 and j <= n
    if A[i, j] == x
      return True
    else if A[i, j] < x
      j = j + 1
    else
      i = i - 1
  return 0

这个算法的基本思想是从左下角查找到右上角，查找每一行\(A[i,j]< x,a[i,j+1]>x\)的边界。由于每一轮循环中，要么\(i\)减去\(1\)，要么\(j\)增加\(1\)，因此这个循环最多执行\(n+m-1\)次。算法FIND-Y时间复杂度为\(O(n+m)\)。