算法导论4.4 Exercises 答案

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

4.4-1

a

  • 第\(0\)层有\(1\)个节点，每个节点的权值为\(n^3\)，权值之和为\(n^3\)。
  • 第\(1\)层有\(1\)个节点，每个节点的权值为\(\dfrac{n^3}{8}\)，权值之和为\(\dfrac{n^3}{8}\)。
  • 第\(2\)层有\(1\)个节点，每个节点的权值为\(\dfrac{n^3}{64}\)，权值之和为\(\dfrac{n^3}{64}\)。
  • ……
  • 第\(i\)层有\(1\)个节点，每个节点的权值为\(\dfrac{n^3}{8^i}\)，权值之和为\(\dfrac{n^3}{8^i}\)。

可以知道，这棵树有\(\lg n\)层，那么有

\(\begin{aligned} T(n)&= \sum_{i=0}^{\lg n} \dfrac{n^3}{8^i}\\ &\le n^3 \sum_{i=0}^{\infty} \dfrac{1}{8^i}\\ &=\dfrac{8}{7} n^3 \end{aligned}\)

那么猜测\(T(n)=O(n^3)\)。使用代入法验证，假设\(T(n)\le cn^3\)，那么有

\(\begin{aligned} T(n)&= T(n/2)+n^3\\ &\le\left(\dfrac{c}{8}+1\right)n^3\\ &\le cn^3 &\qquad(A) \end{aligned}\)

其中步骤\((A)\)假设了\(\dfrac{c}{8}+1\le c\)，即\(c\ge\dfrac{8}{7}\)。

那么令\(c=\max\{8/7,T(1),T(2)/8\}\)。由数学归纳法，\(T(n)=O(n^3)\)成立。

b

  • 第\(0\)层有\(1\)个节点，每个节点的权值为\(n\)，权值之和为\(n\)。
  • 第\(1\)层有\(4\)个节点，每个节点的权值为\(\dfrac{n}{3}\)，权值之和为\(\dfrac{4n}{3}\)。
  • 第\(2\)层有\(16\)个节点，每个节点的权值为\(\dfrac{n}{9}\)，权值之和为\(\dfrac{16n}{9}\)。
  • ……
  • 第\(i\)层有\(4^i\)个节点，每个节点的权值为\(\dfrac{n}{3^i}\)，权值之和为\(\left(\dfrac{4}{3}\right)^in\)。

可以知道，这棵树有\(\log_3n\)层，那么有

\(\begin{aligned} T(n)&= \sum_{i=0}^{\log_3 n} \left(\dfrac{4}{3}\right)^in\\ &= n \sum_{i=0}^{\log _3 n} \left(\dfrac{4}{3}\right)^i\\ &=n\left(\left(\dfrac{4}{3}\right)^{\log_3 n+1} - 3\right) \\ &\le n \left(\dfrac{4}{3}\right)^{\log_3 n+1}\\ &=\dfrac{4}{3} \cdot 4^{\log_3 n}\\ &=\dfrac{4}{3} \cdot n^{\log_3 4}\\ \end{aligned}\)

那么猜测\(T(n)=O(n^{\log_3 4})\)。使用代入法验证，假设\(T(n)\le cn^{\log_3 4}-dn\)，那么有

\(\begin{aligned} T(n)&= 4T(n/3)+n\\ &\le 4c\left(\dfrac{n}{3}\right)^{\log_3 4}-4dn+n\\ &= 4c\cdot\dfrac{n^{\log_3 4}}{4}-4dn+n\\ &= c\cdot n^{\log_3 4}-(4d-1)n\\ &= cn^{\log_3 4}&\qquad(A) \end{aligned}\)

其中步骤\((A)\)假设了\(4d-1\ge d\)，即\(d\ge\dfrac{1}{3}\)。

那么最终令\(c=\max\{1,T(1),T(2)/2^{\log_3 4},T(3)/4\}\)。由数学归纳法，\(T(n)=O(n^{\log_3 4})\)成立。

c

  • 第\(0\)层有\(1\)个节点，每个节点的权值为\(n\)，权值之和为\(n\)。
  • 第\(1\)层有\(4\)个节点，每个节点的权值为\(\dfrac{n}{2}\)，权值之和为\(2n\)。
  • 第\(2\)层有\(16\)个节点，每个节点的权值为\(\dfrac{n}{4}\)，权值之和为\(4n\)。
  • ……
  • 第\(i\)层有\(4^i\)个节点，每个节点的权值为\(\dfrac{n}{2^i}\)，权值之和为\(2^in\)。

可以知道，这棵树有\(\lg n\)层，那么有

\(\begin{aligned} T(n)&= \sum_{i=0}^{\lg n} 2^i n\\ &= n \sum_{i=0}^{\lg n} 2^i\\ &=n \cdot (2^{\lg n+1} - 1)\\ &\le n 2^{\lg n+1} \\ &=2n^2 \end{aligned}\)

那么猜测\(T(n)=O(n^2)\)。使用代入法验证，假设\(T(n)\le cn^2 - dn\)，那么有

\(\begin{aligned} T(n)&=4T(n/2)+n\\ &\le 4(c(n/2)^2 - d(n/2))+n\\ &=cn^2+(1-2d)n\\ &\le cn^2-dn &\qquad(d\ge 1) \end{aligned}\)

取好\(d\)后，令\(c=\max\{1,T(1)+d,(T(2)+2d)/4\}\)。由数学归纳法，\(T(n)=O(n^2)\)成立。

d

  • 第\(0\)层有\(1\)个节点，每个节点的权值为\(1\)，权值之和为\(1\)。
  • 第\(1\)层有\(3\)个节点，每个节点的权值为\(1\)，权值之和为\(3\)。
  • 第\(3\)层有\(9\)个节点，每个节点的权值为\(1\)，权值之和为\(9\)。
  • ……
  • 第\(i\)层有\(3^i\)个节点，每个节点的权值为\(3^i\)，权值之和为\(3^i\)。

可以知道，这棵树有\(n\)层，那么有

\(\begin{aligned} T(n)&= \sum_{i=0}^{n} 3^i\\ &=\dfrac{3^{i+1}-1}{2}\\ &\le\dfrac{3^{i+1}}{2}\\ \end{aligned}\)

那么猜测\(T(n)=O(3^n)\)。使用代入法验证，假设\(T(n)\le c3^n - d\)，那么有

\(\begin{aligned} T(n)&=3T(n-1)+1\\ &\le 3(c\cdot 3^{n-1}-d)+1\\ &=c3^n-(3d-1)\\ &\le c3^n-d & \qquad(A) \end{aligned}\)

其中步骤\((A)\)假设了\(3d-1\ge d\)，即\(d\ge \dfrac{1}{2}\)。

确定好\(d\)值后，令\(c=\max\{1,(T(1)+d)/3\}\)。由数学归纳法，\(T(n)=O(3^n)\)成立。

4.4-2

假设\(L(n)\ge cn\)，那么有

\(L(n)=L(2n/3)+L(n/3)\ge 2cn/3+cn/3=cn\)

考虑当\(n\ge n_0\)时，令\(c=\min\{1,\min_{i=n_0}^{3n_0}\{T(i)/i\}\}\)。由数学归纳法，\(L(n)=\Omega(n)\)成立。

由于已知\(L(n)=O(n)\)，因此\(L(n)=\Theta(n)\)。

4.4-3

假设\(L(n)\ge cn\lg n\)，那么有

\(\begin{aligned} T(n)&=T(n/3)+T(2n/3)+\Theta(n)\\ &\ge c(n/3) \lg(n/3) + c(2n/3)\lg(2n/3)+\Theta(n)\\ &=cn\lg n - \dfrac{\lg (27/4)}{3} cn+\Theta(n)\\ &\ge cn\lg n & \qquad(A)\\ \end{aligned}\)

其中步骤\((A)\)假设了\(\dfrac{\lg (27/4)}{3} cn\)不超过\(\Theta(n)\)的上界。

在此基础上，如果\(c\le \min\{T(2)/2,T(3)/(3\lg 3)\}\)。由数学归纳法，\(T(n)=\Omega(n\lg n)\)成立。

由于已知\(L(n)=O(n\lg n)\)，因此\(L(n)=\Theta(n \lg n)\)。

4.4-4

不失一般性，假设\(0.5\le \alpha <1\)，因为\(\alpha '=1-\alpha\)时的情形是一样的。

可以知道，这棵树的每一层的节点权值之和都为\(\Theta(n)\)。并且这一棵树的高度为\(\log_\alpha (1/n)=\log_{1/\alpha} n\)，那么有

\(\begin{aligned} T(n)&=\sum_{i=0}^{\log_{1/\alpha} n-1}\Theta(n)\\ &=\log_{1/\alpha} n \cdot \Theta(n) \\ &=\Theta(n\lg n) \\ \end{aligned}\)

猜测\(T(n)=O(n\lg n)\)。使用代入法验证，假设\(T(n)\le cn\lg n\)，那么有

\(\begin{aligned} T(n)&=T(\alpha n)+T((1-\alpha)n)+\Theta(n)\\ &\le c\alpha n\lg(\alpha n) + c((1-\alpha) n)\lg((1-\alpha) n)+\Theta(n)\\ &=cn\lg n+c(\alpha\lg \alpha +(1-\alpha)\lg(1-\alpha)) n + \Theta(n)\\ &\le cn\lg n & \qquad(A) \end{aligned}\)

其中\((A)\)步骤基于以下假设，\(\alpha\lg \alpha +(1-\alpha)\lg(1-\alpha)<0\)，因此取恰当大的\(c\)，使得\(-c(\alpha\lg \alpha +(1-\alpha)\lg(1-\alpha))n\)超过\(\Theta(n)\)的上界。

此外，\(c\)还需要满足\(c\ge \max\{1,T(2)/2,T(3)/(3\lg 3)\}\)。由数学归纳法，\(T(n)=O(n\lg n)\)成立。

猜测\(T(n)=\Omega(n\lg n)\)。使用代入法验证，假设\(T(n)\ge c'n\lg n\)，那么有

\(\begin{aligned} T(n)&=T(\alpha n)+T((1-\alpha)n)+\Theta(n)\\ &\ge c'\alpha n\lg(\alpha n) + c'((1-\alpha) n)\lg((1-\alpha) n)+\Theta(n)\\ &=c'n\lg n+c'(\alpha\lg \alpha +(1-\alpha)\lg(1-\alpha)) n + \Theta(n)\\ &\ge cn\lg n & \qquad(A) \end{aligned}\)

其中\((A)\)步骤基于以下假设，\(\alpha\lg \alpha +(1-\alpha)\lg(1-\alpha)<0\)，因此取恰当小的\(c\)，使得\(-c(\alpha\lg \alpha +(1-\alpha)\lg(1-\alpha))n\)不超过\(\Theta(n)\)的上界。

此外，\(c'\)还需要满足\(c\le \min\{1,T(2)/2,T(3)/(3\lg 3)\}\)。由数学归纳法，\(T(n)=\Omega(n\lg n)\)成立。

因此，\(T(n)=\Theta(n\lg n)\)。