发帖
雷达卡
1555688998(1).png
CHAPTER 2
Algorithm Analysis
2.1 2/N, 37, , N, N log log N, N log N, N log(N2), N log2 N, N1.5, N2, N2 log N, N3, 2N/2, 2N.
N log N and N log (N2) grow at the same rate.
2.2 (a) True.
(b) False. A counterexample is T1(N) = 2N, T2(N) = N, and f (N) = N.
(c) False. A counterexample is T1(N) = N2, T2(N) = N, and f (N) = N2.
(d) False. The same counterexample as in part (c) applies.
2.3 We claim that N log N is the slower growing function. To see this, suppose otherwise. Then, would grow slower than log N. Taking logs of both sides, we find that, under this assumption, grows slower than log log N. But the first expression simplifies to If L = log N, then we are claiming that grows slower than log L, or equivalently, that 2L grows slower than log2 L. But we know that log2 L = o(L), so the original assumption is false, proving the claim.
2.4 Clearly, if k1 < k2, so we need to worry only about positive integers. The claim is clearly true for k = 0 and k = 1. Suppose it is true for k < i. Then, by L’Hôpital’s rule,
The second limit is zero by the inductive hypothesis, proving the claim.
2.5 Let f(N) = 1 when N is even, and N when N is odd. Likewise, let g(N) = 1 when N is odd, and N when N is even. Then the ratio f(N)/g(N) oscillates between 0 and inf.
答案如上
预览更多加我V信：ID
答案为本人自己创作，如有雷同，纯属巧合
本文来自: 人大经济论坛 现金交易版 版，详细出处参考： https://bbs.pinggu.org/forum.php ... mp;from^^uid=11596612
Chapter01.doc
(69.5 KB)
京公网安备 11010802022788号
