【算法设计与分析】04 函数的渐进的界

ゞ浴缸里的玫瑰 2021-12-22 08:19 291阅读 0赞

今天学习函数的渐进的界，会涉及多种数学符号。对以后学习分析算法复杂度有很大的帮助。

## 1 大 O O O符号 ##

*  定义： 设 f 和 g是定义域为自然数集N上的函数. **若存在正数 c 和 n0**， 使得  
    对一切 n  ≥ \\geq ≥ n0有:  
     c ≤ f ( n ) ≤ c g ( n ) c\\leq f(n) \\leq cg(n) c≤f(n)≤cg(n)  
    成立。则称f(n)的渐近的上届是g(n)。记作：  
     f ( n ) = O ( g ( n ) ) f(n)=O(g(n)) f(n)=O(g(n))

> 例子：
> 
>  *  设 f ( n ) = n 2 + 2 f(n)=n^2+2 f(n)=n2\+2,则  
>      f ( n ) = O ( n 2 ) , 取 c = 2 ， n 0 = 1 即 可 f(n)=O(n^2),取c=2，n\_0=1即可 f(n)=O(n2),取c=2，n0=1即可  
>      f ( n ) = O ( n 3 ) , 取 c = 3 ， n 0 = 2 即 可 f(n)=O(n^3),取c=3，n\_0=2即可 f(n)=O(n3),取c=3，n0=2即可

对于大 O O O符号，有一下几条概念需要注意：

1.   f ( n ) = O ( g ( n ) ) , f ( n ) 的 阶 不 高 于 g ( n ) 的 阶 f(n)=O(g(n)),f(n)的阶不高于g(n)的阶 f(n)=O(g(n)),f(n)的阶不高于g(n)的阶
2.  可能存在多个正数c，只要指出其中一个即可，
3.  对前面有限个值可以不满足不等式
4.  常函数可以写成 O ( 1 ) O(1) O(1)。

## 2 大 Ω \\Omega Ω符号 ##

*  定义：设 f 和 g是定义域为自然数集N上的函数. **若存在正数 c 和 n0**，使得对一切 n  ≥ \\geq ≥ n0有：

0 ≤ c g ( n ) ≤ f ( n ) 0\\leq cg(n)\\leq f(n) 0≤cg(n)≤f(n)  
成立。则称 f ( n ) f(n) f(n)的渐近的下届是 g ( n ) g(n) g(n)，记作：  
 f ( n ) = Ω ( g ( n ) ) f(n)=\\Omega(g(n)) f(n)=Ω(g(n))

> 例子：
> 
>  *  设 f ( n ) = n 2 + 2 f(n)=n^2+2 f(n)=n2\+2,则  
>      f ( n ) = Ω ( n 2 ) , 取 c = 1 ， n 0 = 1 即 可 f(n)=\\Omega(n^2),取c=1，n\_0=1即可 f(n)=Ω(n2),取c=1，n0=1即可  
>      f ( n ) = Ω ( 100 n ) , 取 c = 1 / 100 ， n 0 = 1 即 可 f(n)=\\Omega(100n),取c=1/100，n\_0=1即可 f(n)=Ω(100n),取c=1/100，n0=1即可

对于 Ω \\Omega Ω符号，需要注意以下几点：

1.   f ( n ) = Ω ( g ( n ) ) , f ( n ) 的 阶 不 低 于 g ( n ) 的 阶 f(n)=\\Omega(g(n)),f(n)的阶不低于g(n)的阶 f(n)=Ω(g(n)),f(n)的阶不低于g(n)的阶
2.  可能存在多个正数c，只要指出其中一个即可
3.  对前面有限个n值可以不满足上述不等式

## 3 小 o o o符号 ##

*  定义：设 f 和 g是定义域为自然数集N上的函数. **若对任意正数 c 都存在 n0**，使得对一切 n  ≥ \\geq ≥ n0有：  
     0 ≤ f ( n ) < c g ( n ) 0 \\leq f(n) < c g(n) 0≤f(n)<cg(n)  
    成立。则记作：  
     f ( n ) = o ( g ( n ) ) f(n) = o(g(n)) f(n)=o(g(n))

> 例子：
> 
>  *  设 f ( n ) = n 2 + 2 f(n)=n^2+2 f(n)=n2\+2,则  
>      f ( n ) = o ( n 3 ) , c ≥ 1 显 然 成 立 。 因 为 n 2 + n < c n 3 （ n 0 = 2 ） f(n)=o(n^3),c\\geq1显然成立。因为n^2+n<cn^3（n\_0=2） f(n)=o(n3),c≥1显然成立。因为n2\+n<cn3（n0=2）  
>      对 于 1 > c > 0 ， 取 n 0 > ⌈ 2 c ⌉ 即 可 ， 因 为 ： 对于1>c>0，取n\_0>\\left \\lceil \\frac\{2\}\{c\} \\right \\rceil即可，因为： 对于1>c>0，取n0>⌈c2⌉即可，因为：  
>      c n ≥ c n 0 > 2 cn\\geq cn\_0>2 cn≥cn0>2 （当n ≥ n 0 \\geq n\_0 ≥n0）  
>      n 2 + n < 2 n 2 < c n 3 n^2+n<2n^2<cn^3 n2\+n<2n2<cn3

对于小 o o o符号，需要注意以下几点：

1.   f ( n ) = o ( g ( n ) ) , f ( n ) 的 阶 低 于 g ( n ) 的 阶 f(n)=o(g(n)),f(n)的阶低于g(n)的阶 f(n)=o(g(n)),f(n)的阶低于g(n)的阶
2.  对不同正数c，n0 不一样，c越小，n0越大。
3.  对前面有限个n值可以不满足上述不等式

## 4 小 ω \\omega ω符号 ##

*  定义：设 f 和 g是定义域为自然数集N上的函数. **若对任意正数 c 都存在 n0**，使得对一切 n  ≥ \\geq ≥ n0有：  
     0 ≤ c g ( n ) < f ( n ) 0 \\leq cg(n) < f(n) 0≤cg(n)<f(n)  
    成立。则记作：  
     f ( n ) = ω ( g ( n ) ) f(n) = \\omega(g(n)) f(n)=ω(g(n))

> 例子：
> 
>  *  设 f ( n ) = n 2 + 2 f(n)=n^2+2 f(n)=n2\+2,则  
>      f ( n ) = ω ( n ) , 不 能 写 f ( n ) = ω ( n 2 ) , 因 为 取 c = 2 ， 不 存 在 n 0 ， 使 得 对 一 切 n ≥ n 0 有 下 式 成 立 f(n)=\\omega(n),不能写f(n)=\\omega(n^2),因为取c=2，不存在n\_0，使得对一切n\\geq n\_0有下式成立 f(n)=ω(n),不能写f(n)=ω(n2),因为取c=2，不存在n0，使得对一切n≥n0有下式成立  
>      c n 2 = 2 n 2 < n 2 + n （ 不 成 立 ） c n^2 = 2n^2< n^2 + n （不成立） cn2=2n2<n2\+n（不成立）

对于小 ω \\omega ω符号，需要注意以下几点：

1.   f ( n ) = ω ( g ( n ) ) , f ( n ) 的 阶 高 于 g ( n ) 的 阶 . f (n)=\\omega (g(n)), f (n)的阶高于g(n) 的阶. f(n)=ω(g(n)),f(n)的阶高于g(n)的阶.
2.   对 不 同 的 正 数 c , n 0 不 等 ， c 越 大 n 0 越 大 . 对不同的正数c, n\_0不等， c 越大n\_0 越大. 对不同的正数c,n0不等，c越大n0越大.
3.  对前面有限个 n 值可以 不满足不等式.

## 5  Θ \\Theta Θ符号 ##

*  定义：若 f ( n ) = O ( g ( n ) ) 且 f ( n ) = Ω ( g ( n ) ) , f(n)=O(g(n))且f(n)=\\Omega(g(n)), f(n)=O(g(n))且f(n)=Ω(g(n)),则记作：

f ( n ) = Θ ( g ( n ) ) f(n)=\\Theta(g(n)) f(n)=Θ(g(n))

> 例子：  f ( n ) = n 2 + n , g ( n ) = 100 n 2 ， 那 么 有 f(n) =n^2 + n, g(n) =100n^2，那么有 f(n)=n2\+n,g(n)=100n2，那么有  
>  f ( n ) = Θ ( g ( n ) ) f(n)=\\Theta (g(n)) f(n)=Θ(g(n))

注意以下两点：

1.   f ( n ) 的 阶 与 g ( n ) 的 阶 相 等 f(n)的阶与g(n)的阶相等 f(n)的阶与g(n)的阶相等
2.  对前面有限个n值，可以不满足条件

## 6 总结 ##

*  五种表示函数的阶的符号： O , Ω , o , ω , Θ O,\\Omega,o,\\omega,\\Theta O,Ω,o,ω,Θ
 *  理解它们的定义
 *  如何用定义证明函数的阶？下一篇文章继续学习。