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 

略。

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


版权声明：本文为hlj-ljz原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/hlj-ljz/p/3387018.html