算法分析与设计第1章习题答案.doc

《算法分析与设计第1章习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章习题（1-1,1-2,1-3,1-6）1-1求下列函数的渐进表达式3n2+10n=O(n2)n2/10+2n=O(2n)21+1/n=O(1)logn3=O(logn)10log3n=O(n)知识点：如果存在正的常数C和自然数N0，使得：当N>=N0时有f(N)<=Cg(N)，则称f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)).这时，可以说f(N)的阶不高于g(N)的阶。1-2论O(1)和O(2)的区别O(1)和O(2)差别仅在于其中的常数因子，根据渐进上界记

2、号O的定义可知，O(1)=O(2)。1-3从低到高排列以下表达式（按渐进阶排列以下表达式）结果：2lognn2/320n4n23nn!分析：当n>=1时，有logn=7时，有3n=4时，有logn>n1/31-6对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=W(g(n))或f(n)=Q(g(n))。知识点：f(n)的阶不高于g(n)的阶：f(n)=O(g(n))；f(n)的阶不低于g(n)的阶：f(n)=W(g(n))；f(n)与g(n)

3、同阶：f(n)=Q(g(n))(1)f(n)=logn2;g(n)=logn+5f(n)与g(n)同阶，故f(n)=Q(g(n))(2)f(n)=logn2;g(n)=n1/2当n>=8时，f(n)<=g(n)，故f(n)=O(g(n))分析：此类题目不易直接看出阶的高低，可用几个数字代入观察结果。如依次用n=1,21,22,23,26,28,210(3)f(n)=n;g(n)=log2nf(n)=W(g(n))(4)f(n)=nlogn+n;g(n)=lognf(n)=W(g(n))(5)f(n)=

4、10;g(n)=log10f(n)=Q(g(n))(6)f(n)=log2n;g(n)=lognf(n)=W(g(n))(7)f(n)=2n;g(n)=100n2f(n)=W(g(n))(8)f(n)=2n;g(n)=3nf(n)=O(g(n))