算法分析4(MIT)英文版完整版

1、 举例： (1)因为对所有的N1有3N4N，我们有3N =(N)； (2)因为当N1时有N+10241025N，我们有N +1024=(N)； (3)因为当N10时有2N 2+11N -103N 2，我们有 2N 2+11N -10=(N 2)； (4)因为对所有N1有N 2N 3，我们有 N2=(N 3)； (5)作为一个反例N 3(N 2)。因为若不然，则存 在正的常数C和自然数N0，使得当NN0时有N3C N 2，即NC 。显然当取N =max(N0,C+l)时这个 不等式不成立，所以N3(N 2)。 Since O-notation describes an upper bound,

2、when we use it to bound the worst-case running time of an algorithm, we have a bound on the running time of the algorithm on every input. Thus, the O(n2) bound on worst-case running time of insertion sort also applies to its running time on every input. The (n2) bound on the worst-case running time

3、of insertion sort, however, does not imply a (n2) bound on the running time of insertion sort on every input.For example, we saw in Chapter 2 that when the input is already sorted, insertion sort runs in (n) time. 根据记号的定义，用它评估算法的复杂 性，得到的只是当规模充分大时的一个上界。 这个上界的阶越低则评估就越精确，结果就越 有价值。 用评估算法的复杂性，得到的只是该复 杂性的

4、一个下界。这个下界的阶越高，则评估 就越精确，结果就越有价值。 明白了记号和之后，记号将随之清楚，因为我 们定义f(N)=(g(N) 则f(N)=(g(N) 且 f(N)=(g(N)。这时，我们说f(N)与g(N)同阶。 -notation Math: (g(n) = f (n) : there exist positive constants c1, c2, and n0 such that 0 c1 g(n) f (n) c2 g(n) for all n n0 Asymptotic performance When n gets large enough, a (n2) algorith

5、m always beats a (n3) algorithm. Asymptotic performance We should not ignore asymptotically slower algorithms, however. Real-world design situations often call for a careful balancing of engineering objectives. Asymptotic analysis is a useful tool to help to structure our thinking. Conclusions (n lg n) grows more slowly than (n2). Therefore, merge sort asymptotically beats insertion sort in the worst case. In practice, merge sort beats insertion sort for n 30 or so. Go test it out for yourself!(实验1） 结论： 对于低效的算法，计算机的计算 速度成倍乃至数10倍地