算法导论第三版习题4.4_算法导论课后习题4.4-6

4.4-1

画出递归树可知：递归树深度为$log_2 n$，第$i$层共有$3^i$个节点，每个节点的代价为$(\frac{1}{2})^i n$，故第$i$层总代价为$(\frac{3}{2})^i n$，
递归树叶子在第$log_2 n$层，则一共有$3^{log_2 n}$片叶子，
设叶子代价为$\Theta(1)$,则叶子总代价为

$$\begin{align} \Theta(3^{log_2 n})=\Theta(n^{log_2 3}) \end{align}$$
则整棵树的代价为
$$\begin{align} T(n) & =c\sum_{i = 0}^{log_2 n - 1}(\frac{3}{2})^in + \Theta(n^{log_2 3})\\ & =cn\cdot \frac{(\frac{3}{2})^{log_2 n} - 1}{\frac{3}{2} - 1} + \Theta(n^{log_2 3})\\ & = 2cn\cdot (\frac{3}{2})^{log_2 n} - 2cn + \Theta(n^{log_2 3})\\ & = 2cn\cdot n^{log_2 \frac{3}{2}} - 2cn + \Theta(n^{log_2 3})\\ & = 2cn^{log_2 3}-2cn+\Theta(n^{log_2 3})\\ & = \Theta(n^{log_2 3}) \end{align}$$
故可猜测 $T(n) = \Theta(n^{log_2 3})$
我们来证明 $T(n) \le cn^{log_2 3} + dn$
$$\begin{align} T(n)&\le 3T(\lfloor n/2\rfloor)+ n\\ &\le3c(\lfloor n/2\rfloor)^{log_2 3} + 2d(\lfloor n/2 \rfloor) + n\\ &\le 3cn^{log_2 3} + (d + 1)n\\ & \end{align}$$
则当 $d=1$时， $T(n)\le3cn^{log_2 3}+dn$
则 $T(n)=O(n^{log_2 3})$

4.4-2

画出递归树可以看出，递归树一共有$log_2 n$层，第$i$层有$2^i$个节点,每个节点代价为$[(\frac{1}{2})^in]^2=(\frac{1}{2})^{2i}n^2$,则每层代价为$(\frac{1}{2})^in^2$，
一共有$2^{log_2 n}=n$个叶子，则叶子总代价为$\Theta(n)$
则总代价为

$$\begin{align} T(n) &=\sum_{i=0}^{log_2 n-1}(\frac{1}{2})^in^2+\Theta(n)\\ &\le n^2 \cdot \frac{1}{1-\frac{1}{2}}+\Theta(n)\\ &=2n^2+\Theta(n)\\ &=\Theta(n^2) \end{align}$$
则可猜测 $T(n)=O(n^2)$
现证明 $T(n)\le cn^2$
$$\begin{align} T(n)& \le c(\frac{n}{2})^2 + n^2\\ &=(\frac{c}{4}+1)n^2\\ &=O(n^2) \end{align}$$

4.4-3

个人认为题目有问题，结果并不收敛，应该没有上界

4.4-4

$T(n)=O(n)$

4.4-5

不会

4.4-6

将递归式最浅的叶子的层数乘以每层代价则为总代价的下限

$$\begin{align} T(n)\ge n \cdot log_3 n=\Omega(nlgn) \end{align}$$

4.4-7

画出递归树可知，递归树一共有$log_2 n$层，第$i$层一共有$4^i$个节点，每个节点的代价为$c(\frac{1}{2})^in$,则每层代价为$c2^in$
叶子总数为$4^{log_2 n}=n^2$,则叶子总代价为$\Theta(n^2)$
故总代价为

$$\begin{align} T(n) &=cn\sum_{i=0}^{log_2 n - 1}2^i+\Theta(n^2)\\ &=cn\cdot \frac{2^{log_2 n }- 1}{2-1}+\Theta(n^2)\\ &=cn\cdot(n-1)+\Theta(n^2)\\ &=\Theta(n^2) \end{align}$$