算法导论12 Problems 答案

发表于 更新于 分类于 阅读次数： 本文字数： 5.6k 阅读时长 ≈ 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 TL} d(x,T)+\sum{x\in TR}d(x,T)\
&=0+\sum{x\in TL} (d(x,T_L)+1)+\sum{x\in TR}(d(x,T_R)+1)\
&=\sum{x\in TL} 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(Tn)] &= \dfrac{1}{n!} \sum{T\text{ have } n \text{ nodes}} P(T)\
&=\dfrac{1}{n!} \left(\sum{k=0}^{n-1}\sum{\substack{TL\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{TR\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{TR\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$个节点。并且左子树的形状和右子树的形状无关。因此，如果左子树有$bk$种形状，那么右子树有$b{n-1-k}$种形状。此时整棵树有$bkb{n-1-k}$种形状。

因此，枚举左子树的节点树$k$，有$\displaystyle{bn=\sum{k=0}^{n-1} bkb{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}^nbkb{n-k}\right) +1\
&=\sum{n=1}^{\infty}x^{n}\left(\sum{k=0}^{n-1}bkb{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}$