《算法分析与设计第1章习题答案1-1,1-2,1-3,》由会员分享，可在线阅读，更多相关《算法分析与设计第1章习题答案1-1,1-2,1-3,（3页珍藏版）》请在金锄头文库上搜索。
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)=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)
2、与g(n) 同阶：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)= 10 ; g(n)= log10 f(n)=Q(g(n)(6) f(n)= log2n ; g(n)= lognf(n)=W(g(n)(7) f(n)= 2n ; g(n)= 100 n2f(n)=W(g(n)(8) f(n)= 2n ; g(n)= 3nf(n)=O(g(n)
