算法分析与设计-第1章习题答案-1-1-1-2-1-3-1-6

第一章习题（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)差别仅在于其中的常数因子，根据渐进上界记号O的定义可知，O(1)=O(2)。1-3从低到高排列以下表达式（按渐进阶排列以下表达式）结果：2lognn2/320n4n23nn!分析：当n=1时，有lognn2/3当n=7时，有3nn!补充：当n=4时，有lognn1/31-6对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=(g(n))或f(n)=(g(n))。知识点：f(n)的阶不高于g(n)的阶：f(n)=O(g(n))；f(n)的阶不低于g(n)的阶：f(n)=(g(n))；f(n)与g(n)同阶：f(n)=(g(n))(1)f(n)=logn2;g(n)=logn+5f(n)与g(n)同阶，故f(n)=(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)=(g(n))(4)f(n)=nlogn+n;g(n)=lognf(n)=(g(n))(5)f(n)=10;g(n)=log10f(n)=(g(n))(6)f(n)=log2n;g(n)=lognf(n)=(g(n))(7)f(n)=2n;g(n)=100n2f(n)=(g(n))(8)f(n)=2n;g(n)=3nf(n)=O(g(n))