算法中函数的增长

一、渐近符号

用来算法的渐近运行时间的符号是用定义域为自然集N={0,1,2,3,…,n}的函数定义的。

1、Θ符号

定义：对一个给定的函数g(n)，用Θ(g(n))来表示函数的集合：

Θ(g(n)) = {f(n)：存在正常数c₁,，c₂和n₀,使对所有的n≥n₀，有0≤c₁g(n) ≤f(n) ≤c₂g(n) }，对于任意一个函数f(n)，若存在正常数c₁,，c₂，使得当n充分大时，f(n)能被夹在c₁g(n)和c₂g(n)中间，则f(n)属于集合Θ(g(n))。

通常这种关系表示为“f(n)= Θ(g(n))”，可以理解为f(n)是Θ(g(n))的元素，既存在数学关系：f(n) ∈Θ(g(n))。对于Θ(g(n))的每个成员必须是渐近非负的，既n足够大时f(n)是非负的，同时g(n)也是非负的。

       例如：假设某个算法的时间复杂度为是以n为变量的函数 f(n)=3n² - 4n + 1，现在我们需要证明f(n)= Θ(n²)，既：该算法的时间复杂度为Θ(n²)。

证明：由上得：f(n)= 3n² - 4n + 1，c₁,和c₂都为正常数，g(n)=n^2,，且0≤c₁g(n) ≤f(n) ≤c₂g(n)，则存在：

              c₁n²≤3n² - 4n + 1 ≤c₂n²

两边都除以n²，得

              c₁≤ 3- 4/n + 1/n² ≤c₂

则左边取c₁≤5/4，对于所有n≥2均成立；

同理右边取c₂≥0，对于所有n≥1均成立。

则n₀可以取值为2；固可以证明：3n² - 4n + 1=Θ(n²)。

简单来说，对于c₁≤ 3- 4/n + 1/n² ≤c₂ 可以理解为当n无限大时，3- 4/n + 1/n² 趋近于一个常数，当n趋近于n₀(某个常数)时，3- 4/n + 1/n² 也趋近于一个常数。

 

f(n)=3n² - 4n + 1，f(n)= Θ(n³)是否成立。

同理得：c₁ n³≤3n² - 4n + 1 ≤c₂ n³

得：       c₁≤ 3/n- 4/n² + 1/n³ ≤c₂

此时3/n- 4/n² + 1/n³随着n的变化而，不成立。

2、O符号

Θ符号是给出函数的的上界和下界的，现在我们更关心的是函数的上界。

定义：O(g(n)) = {f(n)：存在常数c和n₀，使对所有的n≥n₀，有0≤f(n) ≤cg(n)}

证明忽。

注意，函数Θ(n²)是O(g(n))的一个集合。

O符号常用于表示一个算法的最坏情况。

 

 

 

3、Ω符号

O表示一个算法的最坏情况，则Ω通常标示一个算法的最佳情况。

定义：

Ω(g(n)) = {f(n): 存在常数c和n₀，使对所有的n≥n₀，有0≤cg(n) ≤f(n)}

证明略。

定理：对于任意两个函数，f(n)和g(n)，f(n)= Θ(g(n)，当且仅当f(n)=O(g(n)和

f(n)= Ω(g(n))。

可以使用集合来理解，由于O(g(n))表示上界，Ω(g(n))表示下界，则Θ(g(n)是夹在中间的集合。

 

总结，对于算法中的这三个符号是常用的三个符号。lz看一些算法书时候，常常不知道这些公式怎么得来，所以翻了一些资料，参考了《算法导论》、《计算机程序设计》等书籍。对于这三个符号的介绍，lz只是做了肤浅的简介，一些入门级的简介，如果需要深入了解的可以去参考《算法导论》、《计算机程序设计》，这些书籍是经典中的经典。通常会涉及到一些数学逻辑以及数学推理。

(注：大神手下留情，如果出错，望指出错误)