算法分析渐进符号

算法分析渐进符号

渐近记号

Θ（西塔）      ：紧渐近界                相当于\"=\"O （大欧）     ：渐近上界                相当于\"<=\"o（小欧）       ：非紧的渐近上界      相当于\"<\"Ω（大欧米伽）：渐近下界                相当于\">=\"ω（小欧米伽）：非紧的渐近下界       相当于\">\"

用集合论来表示这5个符号的关系

如果f(n)=ω(g(n))，则f(n)=Ω(g(n))

因此对于这些渐近记号的使用最准确应该是“f(n)∈ O (g(n))”，但是一般都是写成“f(n)=O(g(n))”

例如:span style=\"font-size: inherit;\

常用的函数阶

所有这些函数都处于趋近于无穷大的情况下，增长得慢的函数列在上面

常数阶

O(1)

对数阶

O(logN)

多对数阶

线性阶，次线性阶

O(N)

迭代对数阶

O( log(log(N)) )

线性对数阶

O(nlogN)

平方阶

O(n^2)

多项式阶/代数阶

指数阶/几何阶

O(N^n)

阶乘

O(n!)