渐进记法(O,Ω,Θ)

时间:2024-07-08 20:34:50

第一次在《算法导论》中看到这三种渐进记法的符号,当时对此一窍不通,所以也就没有注意它们,直接把他们忽略了,知道学习算法的时候,才知道当初的做法有多傻,因为一个算法的好坏以及复杂度,可以用它们来表示。现在我学习过程当中用的最多的是O(g(n)),大概是老师认为我们还不具有算法设计分析与优化的能力吧。

先声明一下:本文不会对算法的时间复杂度和空间复杂度进行讨论,大家可以查看别的博客。^_^

好了,首先介绍一下这三个符号吧。

符号 含义
O 渐进小于或等于
Ω 渐进大于或等于
Θ 渐进等于

其实大家一看到本文的标题,就应该猜到这几个符号的用法与高等数学有关,因为“渐进”两个字,比如在高等数学中经常听到渐进线之说。

请看以下两个举例:

如果a=x^2+x,b=x^2+5,则称a与b是相同等级的,且a渐进等于b;

如果a=x^2+x,b=x^3+5,则称a与b不是相同等级的,且a渐进小于或等于b,b渐进大于或等于a。

其中判断a和b是不是两个相同等级的,是依靠比较两个式子中自变量最高的次数,a=x^2+x中自变量最高次数为2,b=x^3+5中自变量最高次数为3。

如果两个自变量的最高次数相同,则说明它们是相同等级的,即他们俩渐进相等,如果其中一个的次数比另一个高,则称次数低的一个式子渐进小于或等于次数高的式子,次数高的一个式子渐进大于或等于次数低的式子。注意不要关注他们的系数谁大谁小。

现在用符号表示语言:

a=x^2+x,b=x^2+5;====>a=Θ(b);

a=x^2+x,b=x^3+5;====>a=O(b)或者b=Ω(a);

其实,这个只要明白比较的是什么就能理解三个符号的含义及用法了。

简记为:O表示上界,Ω表示下界,Θ表示平行。