算法分析渐进符号

<ul><li>Θ（西塔）&nbsp; &nbsp; &nbsp; ：紧渐近界&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 相当于"="</li><li>O&nbsp;（大欧）&nbsp; &nbsp; &nbsp;：渐近上界&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 相当于"&lt;="</li><li>o（小欧）&nbsp; &nbsp; &nbsp; &nbsp;：非紧的渐近上界&nbsp; &nbsp; &nbsp; 相当于"&lt;"</li><li>Ω（大欧米伽）：渐近下界&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 相当于"&gt;="</li><li>ω（小欧米伽）：非紧的渐近下界&nbsp; &nbsp; &nbsp; &nbsp;相当于"&gt;"</li></ul>

如果f(n)=Θ(g(n)),&nbsp; 则f(n)=O(g(n))且f(n)=Ω(g(n))

如果f(n)= o (g(n)),&nbsp; 则f(n)=O(g(n))

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

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

<span style="font-size: inherit;">例如:</span><br style="font-size: inherit;"><ul><li><span style="font-size: inherit;">O(n^2)可以是n,2n,1,2n^2等。</span></li><li><span style="font-size: inherit;">Θ(n^2)可以是n^2,3n^2等。</span></li><li><span style="font-size: inherit;">ω(n^2)可以是n^3,n^10等,但不能是n^2。</span></li><li><span style="font-size: inherit;">Ω(n^2)可以是n^2,n^3,n^10等。</span></li><li><span style="font-size: inherit;">o(n^2)可以是n,1,3n等,但不能是n^2。</span></li></ul><br>

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

常数阶

对数阶

多对数阶

线性阶，次线性阶

迭代对数阶

线性对数阶

平方阶

多项式阶/代数阶

指数阶/几何阶

阶乘