计算机算法设计与分析(第4版)-王晓东习题解答.pdf

第一章 作业 1. 证明下列Ο、Ω和Θ的性质 1） f=Ο(g)当且仅当g=Ω(f) 证明：充分性。若f=Ο(g)，则必然存在常数c 0 和n ，使得nn ，有f 1 0 0 c *g(n)。由于c 0，故g(n) 1/ c *f(n)，故g=Ω(f) 。 1 1 1 必要性。同理，若g=Ω(f)，则必然存在c 0 和n ，使得nn ，有g(n) c 2 0 0 2 *f(n). 由于c 0，故f(n) 1/ c *f(n)，故f=Ο(g)。 2 2 2） 若f=Θ (g)则g=Θ (f) 证明：若f=Θ (g)，则必然存在常数c 0 ，c 0 和n ，使得nn ，有c *g(n) 1 2 0 0 1 f(n) c *g(n)。由于c 0，c 0，f(n) c *g(n)可得g(n) 1/c *f(n)，同时， 2 1 2 1 1 f(n) c *g(n)，有g(n) 1/c *f(n)，即1/c *f(n) g(n)  1/c *f(n)，故g=Θ (f)。 2 2 2 1 3） Ο (f+g)= Ο (max(f,g))，对于Ω和Θ同样成立。 证明：设F(n)= Ο (f+g)，则存在c 0 ，和n ，使得nn ，有 1 1 1 F(n) c1 (f(n)+g(n)) = c f(n) + c g(n) 1 1 c *max{f,g}+ c *max{f,g} 1 1 =2 c *max{f,g} 1 所以，F(n)= Ο (max(f,g))，即Ο (f+g)= Ο (max(f,g)) 对于Ω和Θ同理证明可以成立。 4） log(n!)= Θ(nlogn) 1 证明： n n 由于log(n!)= log i log n =nlogn ，所以可得log(n!)= Ο(nlogn) 。 i 1 i 1 由于对所有的偶数n 有， n n n log(n!)= log i log i log n / 2 (n/2)log(n/2)=(nlogn)/2-n/2 。 i 1 i n / 2 i n / 2 当n4 ，(nlogn)/2-n/2(nlogn)/4，故可得n4 ，log(n!) (nlogn)/4，即log(n!)= Ω(nlogn) 。 综合以上两点可得log(n!)= Θ(nlogn) 2. 设计一个算法，求给定n 个元素的第二大元素，并给出算法在最坏情况 下使用的比较次数。（复杂度至多为2n-3 ） 算法： Void findsecond(ElemType A[])