量的等级
?第一个关系符号?：某个函数比另一个函数的增长趋势更快
f(n)f(n)?g(n)?lim?0n??g(n)?传递性：
f?g,g?h?f?h?使用符号?可对常见的函数做一个排序
(1)1,(2)loglogn,(3)logn,(4)n,(5)n,(6)n2015-4-14
?clogn,(7)c,(8)n,(9)c?c9
nncn计算复杂度取这些函数的算法有哪些？
1?loglogn?logn?n?n?nlogn?c?n?cnncn量的等级
?上面排序中的函数都趋向于无穷大。还有另外一种趋向于0的排序11111111???????1n?nnlognc?cncnnnlognloglognc?事实上如果有
11f(n)?g(n),则?g(n)f(n)?对于其它函数，可以尝试放到这个序列的合适位臵
2015-4-1410
量的等级
?例如，对于小于等于n的素数个数函数??n?11由于??n?近似等于nlnn，而1???1?nlnnloglognnn因此???(n)??nnloglognn1???n即n??(n)?loglogn?例如，对于函数elogn由于loglogn?logn??lognlogn?因此logn?e?n2015-4-14
11
量的等级
?当两个函数的增长率相同时，写成正式定义为
?f(n)?cg(n)且有g(n)?cf(n),对于某个c和所有充分大的n2015-4-14
例如对于f(n)?cosn?arctann,g(n)?c?0事实上，如果f(n)和g(n)是次数相同的多项式即有此关系。
?更强的关系~：函数f渐进于函数g
f(n)f(n)~g(n)?lim?1n??g(n)12
