幻想的羽毛

效率分析框架——渐进符号
效率分析框架主要关心算法的基本操作次数的增长次数,并作为一个算法的效率的主要指标。 ----《算法分析与设计基础》...
扫描右侧二维码阅读全文
30
2018/08

效率分析框架——渐进符号

效率分析框架主要关心算法的基本操作次数的增长次数,并作为一个算法的效率的主要指标。
----《算法分析与设计基础》第三版 2.2节

而分析过程中主要用到三个渐进符号

Ο(读作“O”)
Ω(读作“欧米伽”)
Θ(读作“西塔”)

下面通俗讲一下这三个符号的含义:

首先,在上下文中t(n)一般表示一个算法的运行时间,g(n)表示用来和该操作次数做比较的函数


Ο(g(n))

Ο(g(n))表示增长次数小于等于函数g(n)(及其常数倍,n趋向于无穷大)的函数集合

举几个例子:

n ∈ Ο(n²) 

100n+5 ∈ Ο(n²)

½n(n-1) ∈ Ο(n²)

上面例子中前两个左边的函数增长次数都比g(n) = n²要小,而最后一个则和有相同的增长次数

所以总结上来说:

Ο(g(n))表示的是一个算法其增长速率的上限,其上限可以通过函数g(n)描述出来


Ω(g(n))

Ω(g(n))表示增长次数大于等于函数g(n)(及其常数倍,n趋向于无穷大)的函数集合

看下面的例子:

n³ ∈ Ω(n²)

½n(n-1) ∈ Ω(n²)

100n+5 ∉ Ω(n²)

上面例子中,前两个函数的增长趋势都大于或者等于g(n) = n²,而最后一个函数是个线性函数,所以不属于Ω(n²)

所以,总结一下:

Ω(g(n))表示的是一个算法其增长速率的下限,其下限可以通过函数g(n)描述出来


Θ(g(n))

同上面两个符号相比较,Θ(g(n))相对来说比较简单,该符号表示的是其增长次数等于g(n)的函数集合

一个简单的例子:

一个二次方程an²+bn+ca>0的情况下都属于Θ(g(n))


总之,这三个符号在后续的算法分析当中会经常用到,对于理解一些特殊算法,算是基本的知识点

Last modification:August 30th, 2018 at 04:34 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment