算法复杂度分析中的符号(Θ、Ο、ο、Ω、ω)
**
首先要明白两个复杂度:
一个是时间复杂度,一个是渐近时间复杂度。前者是某个算法的时间耗费,它是该算法所求解问题规模n的函数,而后者是指当问题规模趋向无穷大时,该算法时间复杂度的数量级。
Θ,既是上界也是下界(tight),就是相等,准确的复杂度
Ο,表示渐进上界(tightness unknown),小于等于的意思,近似复杂度。
ο,表示上界(not tight),小于的意思,明确的知道小于它,准确计算出来的。
Ω,表示渐进下界(tightness unknown),大于等于的意思,近似复杂度。
ω,表示下界(not tight),大于的意思,明确的知道大于它,准确计算出来的。
顺便补充:
几种常见的复杂度关系
n默认为2,n因为计算机中很多程序是用二分法实现的。