算法导论4.3题

阅读量：

算法导论4.3习题解析

4.3-1 证明：T(n) = T(n-1)+n的解为O(n^2)
- 4.3-2 证明: T(n) = T( $\lceil$ n/2 $\rceil$ ) + 1的解为 $O(\lg n)$
- 4.3-3 我们观察到T(n)=2T( $\lfloor n/2 \rfloor$ ) + n 的解为 $O(n\lg n )$ . 需要验证 $\Omega(n\lg n)$ 是否同样适用于该递归式。由此可得最终结论：该递归式的解为 $\Theta(n\lg n)$ .
- 4.3-4 在进行归纳假设时，若采取不同设定，即可在不改变归纳证明边界条件的前提下，有效解决递归式(4.19)中由T(1)=1所引发的难题。
- 4.3-5 验证：归并排序所对应的严格递归式（4.3）的解为 $\Theta(n\lg n)$
- 4.3-6 验证： $T(n)=2T(\lfloor{n/2}\rfloor+17)+n$ 的解为 $\Theta(n\lg n)$
- 4.3-7 借助第4.5节提及的主定理，可以得出 $T(n) = 4T(n/3)+n$ 的解为 ${T(n)}=\Theta({n^{\log{_3} {4}}})$ . 同时指出，在假设 $T(n) \le{c{n^{\log{_3} {4}}}}$ 的情况下，代入法无法完成该结论的证明。进一步说明如何通

全部评论 (0)

还没有任何评论哟~