渐进表达式 常数间的差异较小 很多情况下，没有意义去说一个运行2n2步的算法 比一个运行n2步的算法要好. 在渐进表式方式中我们忽略常数，这样我们将下面 式子看成相等的： 100n2,1.5n2, n2+4, 10n2-3n+6. 用如下符合表式©(n2). 渐进表式的核心内容就是忽略常数！ 渐进表式是一个被大家认同的计算机里表式运行时间 和空间的方法。 渐进表式系统产生另一个数学系统，与精确数学、模 糊数学、近似数学都不相同
11 渐进表达式 常数间的差异较小 很多情况下，没有意义去说一个运行2n2 步的算法 比一个运行n 2 步的算法要好. 在渐进表式方式中我们忽略常数，这样我们将下面 式子看成相等的: 100n2 , 1.5n2 , n 2+4, 10n2-3n+6. 用如下符合表式 (n2). 渐进表式的核心内容就是忽略常数！ 渐进表式是一个被大家认同的计算机里表式运行时间 和空间的方法。 渐进表式系统产生另一个数学系统，与精确数学、模 糊数学、近似数学都不相同
2.2 Asymptotic Order of Growth (渐进分析)
2.2 Asymptotic Order of Growth (渐进分析)
渐近分析的符号 在下面的讨论中，对所有n,f孔n≥0，g(n)≥0。 (1)渐近上界记号O Og()={fn)|存在正常数c和no使得对所有2n有：0≤f)≤cg(n)] (2)渐近下界记号0 2g()=(fn)丨存在正常数c和no使得对所有2no有：Oscg()≤fn)] (3)紧渐近界记号© ⊙(g(n)=(fn)存在正常数c1,c2和no使得对所有n≥no有：c1g(n)≤fn)≤ c2g(n)} 如果f(n)集合0(g(n))中的一个成员，我们说f(n)属于0(g(n)。 例如： f(n)=32n2+17n+32. f(n)属于0(n2),0(n3),2(n2),2(n),and⊙(n2)· f(n)不属于0(n),2(n3),⊙(n),or⊙(n3). 13
13 渐近分析的符号 在下面的讨论中，对所有n，f(n) 0，g(n) 0。 （1）渐近上界记号O O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n n0有：0 f(n) cg(n) } （2）渐近下界记号 (g(n)) = { f(n) | 存在正常数c和n0使得对所有n n0有：0 cg(n) f(n) } （3）紧渐近界记号 (g(n)) = { f(n) | 存在正常数c1 ,c2和n0使得对所有n n0有：c1g(n) f(n) c2g(n) } 如果 f(n) 集合 O(g(n))中的一个成员，我们说f(n) 属于 O(g(n))。 例如： f(n) = 32n2 + 17n + 32. f(n) 属于 O(n2), O(n3), (n2), (n), and (n2) . f(n) 不属于 O(n), (n3), (n), or (n3)
渐近分析的符号 C28(n) cg(n) f(n) f(n) f() cg(n) c B(n) no fn)=⊙(g(n) f(n)=Og(n)) fn)=2e(r)》 (a) (b) (c) f(n)=@(g(n)) f(n)=O(g(n)) f(n)=2(g(n) 年 立 f(n)=g(n) f(n)≤g(n) f(n)≥g(n) 14
14 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) @ @ @ 渐近分析的符号
更多渐近分析的符号 在下面的讨论中，对所有n,f(n)≥0，g(n)≥0。 (4)非紧上界记号o o(g(n)=(f代)|对于任何正常数c>0,存在正数和no>0使得对所有2no有： 0≤fn)scg(n)]} 等价于fn)/g(n)→0，asn→o。 (5)非紧下界记号0 o(g(n)=〔f孔n)|对于任何正常数c>0,存在正数和no>0使得对所有n≥no有： 0≤cg(n)<f)]} 等价于fn)/g()→o,as n-→0。 f(n∈o(gn)台g(n)∈o(fn) 15
15 更多渐近分析的符号 在下面的讨论中，对所有n，f(n) 0，g(n) 0。 （4）非紧上界记号o o(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n n0有： 0 f(n)<cg(n) } 等价于 f(n) / g(n) 0 ，as n。 （5）非紧下界记号 (g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n n0有： 0 cg(n) < f(n) } 等价于 f(n) / g(n) ，as n。 f(n) (g(n)) g(n) o (f(n))