算法导论4.4 Exercises 答案

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

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 n0$时，令$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)$。