算法导论第三章习题答案（第三版） Introduction to Algorithm

Exercises

3.1-1

因为f (n)与g(n)是渐近非负的，所以存在 ， 使得 f(n),g(n)>0，可以看出存在 ， 使得 ， 所以可以证出max{f(n),g(n)}=Θ(f(n)+g(n))。

3.1-2

根据题意可知， 当 时成立，且 ，当 时成立，因此存在 ， 使得当 时， ， 因为b>0，所以，因此存在 ， 使得 ， 证明完毕。

3.1-3

O(n)已经代表T(n)运行上界，最少是O(n)对于T(n)来说是无法达到的，所以是没有意义的。

3.1-4

1.因为 ，所以成立。

2.不成立，假设成立的话，那么存在c，使得 ，那么 ， 因为c是常数，n可以无限大，所以不可能成立，所以不成立。

3.1-5  略。

3.1-6

O符号给出的是运行的上界，Ω给出的是下界，若f(n)的上下界全是g(n)，那么必定有f(n)=Θ(g(n))。

3.1-7

假设其不为空，那么存在f(n)=(o(g(n))∩(ω(g(n))，也就是说f(n)=o(g(n))=ω(g(n),根据书中的定义， 且 ， 这里矛盾，所以不成立，必为空集。

3.1-8  略。

3.2-1  略。

3.2-2

证明如下：

3.2-3

1.欲证，只需证，使得，对于足够大的n，一定会有，所以时，即可成立。根据斯特林近似公式可得：，故，所以，故，所以，因此当，，取，所以存在正常数时，。

2.略。

3.略。

3.2-4

根据斯特林近似公式和阶数的相关关系即可求得。

3.2-5,6,7,8 

略。

 （若有错误和不足，欢迎大家积极指正！）