ω表示仅仅是大Ω去掉等于的情况,其他行为与大Ω一模一样。
通俗理解 符号 含义 通俗理解Θ 精确的渐近行为 相当于“=”
O 上界 相当于“<=”
o 松上界 相当于“<”
Ω 下界 相当于“>=”
ω 松下界 相当于“>”
小结
为了帮助同学们快速查阅英文资料,彤哥特地把这几节涉及到的英语单词汇总了一下:
汉语 英文复杂度 complexity
时间复杂度 time complexity
空间复杂度 space complexity
渐近分析 asymptotic analysis
最坏情况 the worst case
最好情况 the best case
平均情况 the average case
精确的渐近行为 exact asymptotic behavior
低阶项 low order terms
常数项(前置常数) leading constants
松上界 loose upper-bound
后记
本节,我们分别从读音、数学、通俗理解等三个方面阐述了Θ、O、o、Ω、ω的含义,并在最后给出了这几节涉及到的术语对应的英文,有了这些英文,你也可以快速地查阅这方面的资料。
不过,在我们平时与人交流的过程中,大家还是习惯于使用大O表示法,一来它表示最坏情况,最坏情况通常可以直接代表算法的复杂度,二来它比较好书写。
所以,我们只需要记住大O就可以了,只不过在别人提到Θ、Ω、ω我们知道是什么含义就可以了。
前面几节讲了这么多,其实,还是只涉及了很简单的算法复杂度。
那么,常见的算法复杂度有哪些呢?
下一节,我们接着聊。
关注公号主“彤哥读源码”,解锁更多源码、基础、架构知识。