O、Θ、Ω、o、ω,别再傻傻分不清了! (2)

ω表示仅仅是大Ω去掉等于的情况,其他行为与大Ω一模一样。

通俗理解 符号 含义 通俗理解
Θ   精确的渐近行为   相当于“=”  
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就可以了,只不过在别人提到Θ、Ω、ω我们知道是什么含义就可以了。

前面几节讲了这么多,其实,还是只涉及了很简单的算法复杂度。

那么,常见的算法复杂度有哪些呢?

下一节,我们接着聊。

关注公号主“彤哥读源码”,解锁更多源码、基础、架构知识。

file

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wsxyyy.html