算法导论12 Problems 答案

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

12-1

a

根据算法TREE-INSERT可知，每个相同的键都将会查到当前最深子节点的右儿子，因此第\(i\)次插入需要遍历\(i-1\)个节点。整个过程总共需要遍历\(\dfrac{n(n-1)}{2}\)次的节点，这种情况下总运行时间为\(\Theta(n^2)\)。

b

对于树中任意一个节点，每次插入一个新节点时，选择向左传递和向右传递这个节点是交替的，因此对于任意一个节点而言，左子树比右子树的大小至多大\(1\)，这确保了整棵树的高度为\(\lg n\)，最终总插入时间为\(O(n\lg n)\)。

c

所有相同键的节点都汇集到一个超级节点\(x\)中，整个插入过程最多只需要遍历一个节点，因此每次插入时只需要花费\(O(1)\)的时间，总时间为\(O(n)\)。

d

在最坏情况下，每一次插入都随机选择到同一侧的子节点，此时总时间复杂度将会达到\(O(n^2)\)。

在平均情况下，每一个节点的左右子节点都有同样的选择机会，最终整棵树的期望高度为\(\lg n\)，总插入时间为\(O(n\lg n)\)。

12-2

假设每个节点都有\(3\)个属性：左子节点left，右子节点right，以及从根节点到当前节点路径所代表的字符串的个数count。

这个基数树本质上可以看成是一个只有\(2\)个字符的字典树，并且整个排序过程视为是在字典树上进行遍历。

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
35
36
37
38
39
INSERT-TRIE(T, s)
  if T.root == NIL
    let T.root be a new node
  p = T.root
  for i = 1 to s.size
    if s[i] == '0'
      if p.left == NIL
        let p.left be a new node
      p = p.left
    else
      if p.left == NIL
        let p.right be a new node
      p = p.right
  p.count = p.count + 1

INORDER-TREE-WALK-SORT(p, B, S)
  if p == NIL
    return
  // 第2种情况：如果一个字符串s是另外一个字符串的前缀s'，那么s会比s'更先插入到B中，因为s所代表的节点深度更浅。
  for i = 1 to p.count
    parse S into a string and insert it in B
  // 第1种情况：由于先进入左节点，因此可以满足第1种情况的比较。
  PUSH(S, '0')
  INORDER-TREE-WALK-SORT(p.left, B, S)
  POP(S, '0')
  PUSH(S, '1')
  INORDER-TREE-WALK-SORT(p.right, B, S)
  POP(S, '1')

// 字符串数组A
SORT-BY-RADIX-TRIE(A)
  let T be a new tree
  // 在基数树中插入每个字符串。
  for each s in A
    INSERT-TRIE(T, s)
  let B be a new array
  let S be a new STACK
  INORDER-TREE-WALK-SORT(T.root, B, S)
  return B

插入单个字符串的算法INSERT-TRIE的时间复杂度为\(|s|\)，因为for循环无非就是遍历了整个字符串，而其它新建节点的操作可以视为是\(O(1)\)的操作，因此所有操作的运行时间之和为\(O(n)\)。

假设基数树为\(T\)，那么按照插入算法的第7, 11行可以发现节点数\(|T|\)必定满足\(|T|< n\)，遍历树\(T\)的时间复杂度为\(O(|T|)\)。第3行将栈转化为字符串的操作为\(O(n)\)。最终时间复杂度为\(O(|T|)+O(n)=O(n)\)。

整个过程的时间复杂度为\(O(n)\)。由于输入规模为\(n\)，因此整个过程的时间复杂度也满足\(\Omega(n)\)，最终为\(\Theta(n)\)。

12-3

a

所有节点的深度的平均值为它们节点之和与节点数的商，即\(\displaystyle{\dfrac{1}{n}\sum_{v\in V}d(x,T)=\dfrac{1}{n}P(T)}\)。

b

左子树\(T_L\)内部节点的深度之和为\(P(T_L)\)，右子树\(T_R\)内部节点的深度之和为\(T_R\)。两棵子树使用一个根节点\(r\)连接后，\(T\)中所有非根节点的深度都增加了\(1\)；由于\(T_L\)和\(T_R\)一共有\(n-1\)个节点，因此最终有

\(\begin{aligned} P(T)&=\sum_{x\in T} d(x,T)\\ &=d(r,T)+\sum_{x\in T_L} d(x,T)+\sum_{x\in T_R}d(x,T)\\ &=0+\sum_{x\in T_L} (d(x,T_L)+1)+\sum_{x\in T_R}(d(x,T_R)+1)\\ &=\sum_{x\in T_L} d(x,T_L)+\sum_{x\in T_R}d(x,T_R)+n-1\\ &=P(T_L)+P(T_R)+n-1 \end{aligned}\)

c

令树的集合\(T_n\)表示由\(n!\)个不同排列分别产生的\(n!\)个二叉搜索树。

根据题目的定义，有\(P(n)=E[P(T_n)]\)。那么可以写出

\(\begin{aligned} E[P(T_n)] &= \dfrac{1}{n!} \sum_{T\text{ have } n \text{ nodes}} P(T)\\ &=\dfrac{1}{n!} \left(\sum_{k=0}^{n-1}\sum_{\substack{T_L\text{ have } k \text{ nodes}\\T_R\text{ have } n-k-1 \text{ nodes}}} (P(T_L) +P(T_R)+n-1)\right)\\ &=\dfrac{1}{n!} \left(\sum_{k=0}^{n-1}\sum_{\substack{T_L\text{ have } k \text{ nodes}\\T_R\text{ have } n-k-1 \text{ nodes}}} P(T_L) +P(T_R)\right) +n-1\\ &=\dfrac{1}{n!} \left(\sum_{k=0}^{n-1}(n-k-1)!\cdot\sum_{T_L\text{ have } k \text{ nodes}}P(T_L)+k!\cdot\sum_{T_R\text{ have } n-k-1 \text{ nodes}}P(T_R)\right)+n-1\\ &=\dfrac{1}{n!} \left(\sum_{k=0}^{n-1}(n-1)!\cdot\dfrac{1}{k!}\cdot\sum_{T_L\text{ have } k \text{ nodes}}P(T_L)+(n-1)!\cdot\dfrac{1}{(n-k-1)!}\cdot\sum_{T_R\text{ have } n-k-1 \text{ nodes}}P(T_R)\right)+n-1\\ &=\dfrac{1}{n!} \left(\sum_{k=0}^{n-1}(n-1)!\cdot E[T_{k}]+(n-1)!\cdot E[T_{n-k-1}]\right)+n-1\\ &=\dfrac{1}{n} \left(\sum_{k=0}^{n-1}P(k)+P(n-k-1)\right)+n-1\\ &=\dfrac{1}{n} (\sum_{k=0}^{n-1}P(k)+P(n-k-1)+n-1) \end{aligned}\)

d

\(\begin{aligned} P(n)&=\dfrac{1}{n}\sum_{i=0}^{n-1}(P(i)+P(n-i-1)+n-1)\\ &=\dfrac{1}{n}\sum_{i=0}^{n-1}(P(i)+P(n-i-1))+n-1\\ &=\dfrac{1}{n}\sum_{i=0}^{n-1}P(i)+\dfrac{1}{n}\sum_{i=0}^{n-1}P(n-i-1)+n-1\\ &=\dfrac{2}{n}\sum_{i=0}^{n-1}P(i)+n-1\\ &=\dfrac{2}{n}\sum_{i=0}^{n-1}P(i)+\Theta(n)\\ &=\dfrac{2}{n}\sum_{i=1}^{n-1}P(i)+\Theta(n)&\qquad(A)\\ \end{aligned}\)

步骤\((A)\)应用了\(P(0)=0\)，即一棵空树的高度为\(0\)。

e

根据题目12-3-d导出的关于\(P(n)\)的递推式，发现和题目7-3-c导出的关于\(T(n)\)的递推式完全相同。因此根据题目7-3-e的结论，有\(P(n)=O(n\lg n)\)。

f

可以发现，第一个元素是插入到空树的根当中，往后的所有元素都将会和当前这个元素进行比较。因此在这个新的快速排序算法中，我们选择第一个元素作为支点，这个元素同样将会和数组中的所有元素进行比较。为了确保递归后的比较次数和插入二叉树的比较次数相同，划分后的数组必须保证这一次划分过后，除了支点，其它比支点小的数和比支点大的数相对顺序不变。保证下一次的递归过程是正确的。这个算法由QUICKSORT-EQ-BST给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
QUICKSORT-EQ-BST(A, p, r)
  x = A[p]
  let B be new array
  for j = p + 1 to r
    if A[j] < x
      i = i + 1
      A[j] = A[i]
    else
      INSERT(B, A[j])
  i = i + 1
  j = i
  A[i] = x
  for each x in B
    i = i + 1
    A[i] = x
  QUICKSORT-EQ-BST(A, p, j - 1)
  QUICKSORT-EQ-BST(A, j + 1, r)

12-4

a

考虑使用动态规划的思想进行思考。

对于当前一棵\(n\)个节点的二叉树，如果左子树有\(k\)个节点，那么右子树有\(n-1-k\)个节点。并且左子树的形状和右子树的形状无关。因此，如果左子树有\(b_k\)种形状，那么右子树有\(b_{n-1-k}\)种形状。此时整棵树有\(b_kb_{n-1-k}\)种形状。

因此，枚举左子树的节点树\(k\)，有\(\displaystyle{b_n=\sum_{k=0}^{n-1} b_kb_{n-k-1}}\)。

b

\(\begin{aligned} xB(x)^2+1&=x\left(\sum_{n=0}^{\infty}b_nx^n\right)^2 +1\\ &=x\sum_{n=0}^{\infty}x^n\left(\sum_{k=0}^nb_kb_{n-k}\right) +1\\ &=\sum_{n=0}^{\infty}x^{n+1}\left(\sum_{k=0}^nb_kb_{n-k}\right) +1\\ &=\sum_{n=1}^{\infty}x^{n}\left(\sum_{k=0}^{n-1}b_kb_{n-1-k}\right) +1\\ &=\sum_{n=1}^{\infty}b_nx^{n} +b_0x^0\\ &=\sum_{n=0}^{\infty}b_nx^{n}\\ &=B(x) \end{aligned}\)

将\(xB(x)^2+1=B(x)\)看成是关于\(B(x)\)的一元二次方程\(xB(x)^2-B(x)+1=0\)，可以解得\(B(x)=\dfrac{1\pm\sqrt{1-4x}}{2x}\)，去掉正号后得到\(B(x)=\dfrac{1-\sqrt{1-4x}}{2x}\)。

c

令\(f(x)=\sqrt{1-4x}\)。根据规律可以发现，\(f^{(n)}(x)\)的表达式可以写成：

\(\begin{aligned} f^{(n)}(x) &= -\dfrac{1}{(1-4x)^{(2n-1)/2}}\cdot(2\times (1\times 2)\times(3\times 2)\times\dots\times((2n-3)\times 2))\\ &= -\dfrac{1}{(1-4x)^{(2n-1)/2}}\cdot 2^n\cdot(1\times 3\times\dots\times (2n-3))\\ &= -\dfrac{1}{(1-4x)^{(2n-1)/2}}\cdot 2^n\cdot\dfrac{(2n-2)!}{2\times 4\times 6\times \dots\times(2n-2)}\\ &= -\dfrac{1}{(1-4x)^{(2n-1)/2}}\cdot\dfrac{2\cdot(2n-2)!}{(n-1)!}\\ \end{aligned}\)

可以得知\(f^{(n)}(0)=-\dfrac{2\cdot(2n-2)!}{(n-1)!}\)。将\(f(x)\)在\(x=0\)处泰勒展开，可以写成\(\displaystyle{f(x)=1-\sum_{n=1}^{\infty}\dfrac{2\cdot(2n-2)!}{(n-1)!n!}x^n}\)。将\(B(x)\)在\(x=0\)处代入\(f(x)\)的展开式，有

\(\begin{aligned} B(x)&=\dfrac{1-f(x)}{2x}\\ &=\dfrac{1}{2x} \sum_{n=1}^{\infty}\dfrac{2\cdot(2n-2)!}{(n-1)!n!}x^n\\ &=\sum_{n=1}^{\infty}\dfrac{(2n-2)!}{(n-1)!n!}x^{n-1}\\ &=\sum_{n=0}^{\infty}\dfrac{(2n)!}{n!(n+1)!}x^{n}\\ &=\sum_{n=0}^{\infty}\dfrac{1}{n+1}\dfrac{(2n)!}{n!n!}x^{n}\\ &=\sum_{n=0}^{\infty}\dfrac{1}{n+1}\dbinom{2n}{n}x^{n}\\ \end{aligned}\)

因此有\(b_n=\dfrac{1}{n+1}\dbinom{2n}{n}\)。

d

\(\begin{aligned} b_n&=\dfrac{1}{n+1}\dbinom{2n}{n}\\ &=\dfrac{1}{n+1}\cdot \dfrac{\sqrt{4\pi n}\cdot\left(\dfrac{2n}{e}\right)^{2n}\cdot\left(1+\Theta\left(\dfrac{1}{n}\right)\right)}{\left(\sqrt{2\pi n}\cdot\left(\dfrac{n}{e}\right)^{n}\cdot\left(1+\Theta\left(\dfrac{1}{n}\right)\right)\right)^2}\\ &=\dfrac{1}{n+1}\cdot\dfrac{2\sqrt{\pi n}\cdot\left(2n\right)^{2n}\cdot\dfrac{1}{e^{2n}}}{2\pi n\cdot n^{2n}\cdot \dfrac{1}{e^{2n}}} \cdot\left(1+\Theta\left(\dfrac{1}{n}\right)\right)\\ &=\dfrac{1}{n+1}\cdot\dfrac{2^{2n}}{\sqrt{\pi n}}\cdot \left(1+\Theta\left(\dfrac{1}{n}\right)\right)\\ &=\dfrac{1}{n+1}\cdot \dfrac{2^{2n}}{\sqrt{\pi n}}\cdot \left(1+O\left(\dfrac{1}{n}\right)\right)\\ &=\dfrac{1}{n}\cdot \dfrac{2^{2n}}{\sqrt{\pi n}}\cdot \left(1+O\left(\dfrac{1}{n}\right)\right)\\ &=\dfrac{4^{n}}{\sqrt{\pi}n^{3/2}}\cdot \left(1+O\left(\dfrac{1}{n}\right)\right) \end{aligned}\)