算法导论16 Problems 答案

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

16-1

a

定义二进制反射格雷码序列\(a_k\)的差分序列为\(d(a_k)=\langle a_{k,1}\text{ xor }a_{k,0},a_{k,2}\text{ xor }a_{k,1}\,a_{k,3}\text{ xor }a_{k,2},\dots,a_{k,2^k-1}\text{ xor }a_{k,2^k-2}\rangle\)。也就是说，\(d(a_k)\)的长度为\(2^k-1\)。

现在证明，\(\forall k\ge 1,d(a_k)\)是一个对称的序列。

当\(k=1\)时，可以知道\(d(a_1)=\langle1\rangle\)。这是一个对称的序列。

当\(k>1\)时，按照从\(a_{k-1}\)到\(a_{k}\)的构造可以发现，\(d(a_k)\)的前\(2^{k-1}-1\)个元素和\(d(a_{k-1})\)完全相同，而\(d(a_k)\)的后\(2^{k-1}-1\)个元素恰好是\(d(a_{k-1})\)的逆序\(\text{rev}(d(a_{k-1}))\)，\(d(a_k)\)中间那个元素的值为\(2^{k-1}\)。也就是说，\(d(a_{k})=d(a_{k-1})\Vert\langle 2^{k-1}\rangle\Vert\text{rev}(d(a_{k-1}))\)。因此，\(d(a_k)\)仍然是对称的。

可以发现，\(d(a_k)\)的第\(i\)个元素表示的是最大的整数\(x\)使得\(2^x\mid i\)。那么这个程序的设计和算法INCREMENT非常类似。这个过程将由DETERMINE-FLIP给出。

1
2
3
4
5
6
// I表示这个下标二进制数组，k表示这个数组的大小。
DETERMINE-FLIP(I, k)
  i = 0
  while i < k and I[i] == 0
    i = i + 1
  return i

b

算法GEN-BINARY-REFLECTED-GRAY-CODE给出了产生一个长度为\(2^k\)的\(k\)位反射格雷码算法。这个算法的特点是在第4行执行了\(2^k\)次子程序INCREMENT'。按照前文的分析，这\(2^k\)次执行INCREMENT'的运行时间之和为\(\Theta(2^k)\)。如果for循环中的其它所有单次操作的时间均有常数上限，那么算法GEN-BINARY-REFLECTED-GRAY-CODE的运行时间之和为\(\Theta(2^k)\)。

1
2
3
4
5
6
7
8
9
10
// 假设算法INCREMENT'的过程和INCREMENT完全相同，区别在于INCREMENT'会在最后将i值返回。
GEN-BINARY-REFLECTED-GRAY-CODE(k)
  let I[0 : k], J[0 : k] be new array by 0
  m = pow(2, k)
  for s = 1 to m
    parse J as k-bit binary reflected Gray code and show it
    i = INCREMENT'(I, k)
    // 按照题目条件，这个步骤是常数花费的。
    if i < k
      J[i] ^= 1

16-2

a

直接遍历这\(k\)个数组，每个数组\(A_i\)执行一次二分查找，如果查找到了及时返回，否则继续查找下一个数组。因此在最坏情况下，每个数组都为满且进行了一次查找，因此在最坏情况下这个算法的时间复杂度为\(O\displaystyle{\left(\sum_{i=0}^{k-1} \lg 2^i\right)}\)，即\(O(k^2)=O(\lg^2n)\)。

b

首先简单地将数插入到\(A_0\)，这时只需要花费\(O(1)\)的代价。如果\(A_0\)原本就已满，那么就复制到\(A_1\)中，如果\(A_1\)也是满的，那么有序合并\(A_0,A_1\)，并复制到\(A_2\)中，以此类推，从低级别的数组转移到高级别数组。如果当前有\(n=2^k-1\)个元素，并且再执行一次插入操作，那么就会达到最坏情况。此时数组\(A_0,A_1,A_2\dots,A_{k-1}\)中的所有数都需要清空，合并后放到\(A_{k}\)中。由于合并两个有序数组的开销是线性的，这时将会达到最坏的时间复杂度\(O(2^k)\)，即\(O(n)\)。

考虑INSERT操作的均摊代价。每次操作支付\(1\)美元，用于当前的插入操作，并且预支\(k-1\)美元，用于后续将这个元素从低级数组转移到高级数组。由于这个\(n\)元集合最多只有\(k\)个数组，并且所有元素只会从低级数组转移到高级数组，因此这些操作足以不产生任何的欠费。因此，无论是否处于最坏情况，一个INSERT操作均摊后只需要花费\(O(k)\)的代价，即\(O(\lg n)\)。

c

令\(p\)为最小的整数使得数组\(A_p\)不为空。如果所要删除的元素\(x\)在\(A_p\)，那么删除\(x\)，并以\(O(2^p)\)的时间将\(A_p\)剩余的元素全部转入\(A_0,A_1,\dots,A_{p-1}\)中。否则，假设\(x\)在\(A_q(q>p)\)中，那么从\(A_q\)中删除元素\(x\)，并且从\(A_p\)中挑选一个元素\(x\)放到\(q\)中，以\(O(2^q)\)的时间使序列\(A_q\)有序，接下来就和之前一样，继续将\(A_p\)剩下的所有元素全部转入\(A_0,A_1,\dots,A_{p-1}\)中。

因此，DELETE的单次操作的时间复杂度为\(O(2^q)=O(n)\)。当元素个数恰好为\(2^x-1\)时，轮流进行INSERT, DELETE, INSERT, DELETE, ...操作时将会达到最坏情况，每次产生\(O(n)\)个元素的位置变化，此时均摊分析失效。

最终，单次操作的平均运行时间为\(O(n)\)。

16-3

a

重构出一棵\(\dfrac{1}{2}\)平衡二叉树由算法REBUILD-BALANCED-TREE给出。它先将原本树\(T\)的中序遍历结果求出，使用\(O(T.root.size)\)的空间存储这个结果。然后再以这个中序遍历的结果的中点作为根节点，然后左半部分和右半部分分别进行递归。划分出中点后，左半部分和右半部分的子节点数最多相差\(1\)，因此是满足\(\dfrac{1}{2}\)平衡的条件的。

在算法REBUILD-RUN中，一个中序遍历的结果被均匀划分成两半。令\(T(n)\)表示用长度为\(n\)的序列构造出一棵\(\dfrac{1}{2}\)平衡的二叉树的运行时间，那么有\(T(n)=2T(n/2)+1\)，最终不难得出\(T(n)=\Theta(n)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
REBUILD-RUN(L, p, r)
  if p > r
    return NIL
  m = ⌊(p + r) / 2⌋
  l = REBUILD(L, p, m - 1)
  r = REBUILD(L, m + 1, r)
  L[m].left = l
  L[m].right = r
  return L[m]

REBUILD-BALANCED-TREE(T)
  // 将T的中序遍历结果存放在L中。
  generate inorder traversal list L of T
  T.root = REBUILD-RUN(L, 1, n)
  n = L.size
  return T

b

令\(U(n)\)表示在一棵\(\alpha\)平衡二叉树中进行查找的时间。根据\(\alpha\)平衡的定义，如果当前树的节点个数为\(n\)，那么它的两个子树的节点数都不超过\(\alpha n\)。因此有\(U(n)\le U(\alpha n)+1\)。由于\(\alpha<1\)，根据主定理，可以得到\(U(n)=O(\lg n)\)。

c

由于\(\Delta(x)\)的定义最外部有一个绝对值符号，因此\(\Delta(x)\ge 0\)必定成立。也就是说，\(\Phi(T)\ge 0\)必定成立。

如果一棵树是\(T\)满足\(\Phi(T)=0\)，那么相当于\(\forall x\in T,\Delta(x)\le 1\)均成立。如果一个节点的两棵子树的节点树相等，那么这个节点必定是一个\(\dfrac{1}{2}\)平衡节点；如果一棵子树的节点子树的节点数相差\(1\)，假设左子树为\(x\)，右子树为\(x+1\)，整棵树一共有\(x+x+1+1=2x+2\)个节点，右子树的节点数占比数仍然不超过\(\dfrac{1}{2}\)。因此，如果一棵二叉树\(T\)是一个\(\dfrac{1}{2}\)平衡二叉树，那么\(\Phi(T)=0\)。

d

不失一般性，假设子树\(T\)中的某个节点\(x_0\in T\)不满足\(\alpha\)平衡的情况。那么有\(x_0.left.size>\alpha x_0.size\)。

那么可以推出\(x_0.right.size< x_0.size-\alpha x_0.size-1<(1-\alpha)x_0.size\)。

在这种情况下，有\(\Delta(x_0)=x_0.left.size-x_0.right.size>(2\alpha-1)x_0.size\)。

不考虑\(T\)中的其它节点的情况，可以知道，\(\displaystyle{\Phi(T)=c\sum_{x\in T:\Delta(x)\ge 2}\Delta(x)>c\Delta(x_0)=c(2\alpha-1)x_0.size}\)。

如果\(x.size\)个单位的势能够支付重建\(x.size\)个节点子树的代价，那么有\(\Phi(T)>x_0.size\)，并且每个节点平均只会摊分了常数代价。为了保证此式成立，令\(c(2\alpha-1)x_0.size>x_0.size\)，最终得到\(c>\dfrac{1}{2\alpha}\)。

e

继续进行16-3-d的讨论。每个节点的均摊成本为常数。

由于这棵树是\(\alpha\)平衡的，根据题目16-3-b的结论，无论进行一次插入操作还是进行一次删除操作，都只需要\(O(\lg n)\)的运行时间。需要注意的是，无论是哪种操作，本质上都是在一棵树上的某个节点\(x\)进行操作。操作完成后，只有从根节点\(T.root\)到\(x\)这条路径之间的所有节点都需要进行\(\alpha\)平衡性判断，这条路径上一共有\(O(\lg n)\)个节点。一次操作完成后，如果有多个节点不再满足\(\alpha\)平衡性质，那么就选择深度最浅的那个节点\(p\)进行重构。这次操作导致了路径\(p\)到\(x\)中，所有的\(\Delta\)值都发生了改变。由于这些节点至多有\(O(\lg n)\)个，每个节点的均摊成本为常数，因此进行一次操作的均摊成本为\(O(\lg n)\)。