算法分析渐进符号
2021-05-25 11:51:03 126 举报AI智能生成
算法分析渐进符号
作者其他创作
大纲/内容
渐近记号
- Θ（西塔） ：紧渐近界 相当于"="
- O （大欧） ：渐近上界 相当于"<="
- o（小欧） ：非紧的渐近上界 相当于"<"
- Ω（大欧米伽）：渐近下界 相当于">="
- ω（小欧米伽）：非紧的渐近下界 相当于">"
用集合论来表示这5个符号的关系
如果f(n)=Θ(g(n)), 则f(n)=O(g(n))且f(n)=Ω(g(n))
如果f(n)= o (g(n)), 则f(n)=O(g(n))
如果f(n)=ω(g(n))，则f(n)=Ω(g(n))
因此对于这些渐近记号的使用最准确应该是“f(n)∈ O (g(n))”，但是一般都是写成“f(n)=O(g(n))”
例如:
- O(n^2)可以是n,2n,1,2n^2等。
- Θ(n^2)可以是n^2,3n^2等。
- ω(n^2)可以是n^3,n^10等,但不能是n^2。
- Ω(n^2)可以是n^2,n^3,n^10等。
- o(n^2)可以是n,1,3n等,但不能是n^2。
常用的函数阶
所有这些函数都处于趋近于无穷大的情况下，增长得慢的函数列在上面
常数阶
O(1)
对数阶
O(logN)
多对数阶
线性阶，次线性阶
O(N)
迭代对数阶
O( log(log(N)) )
线性对数阶
O(nlogN)
平方阶
O(n^2)
多项式阶/代数阶
指数阶/几何阶
O(N^n)
阶乘
O(n!)
0 条评论
下一页
