数据结构与算法分析 Java语言描述 原书第三版 韦斯 WEISS 习题答案 源码

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&nbsp;=&nbsp;0 and k&nbsp;=&nbsp;1. Suppose it is true for k < i. Then, by L’H&ocirc;pital’s rule,

         The second limit is zero by the inductive hypothesis, proving the claim.
2.5        Let f(N)&nbsp;=&nbsp;1 when N is even, and N when N is odd. Likewise, let g(N)&nbsp;=&nbsp;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