文章目录
一、渐进上界
二、大 O 记号
三、常用的渐进上界
一、渐进上界
g ( n ) \rm g(n)g(n) 是 f ( n ) \rm f(n)f(n) 的渐进上界 :
存在 c \rm cc , 并且存在 N \rm NN , 使得任何 n \rm nn , 并且 n ≥ N \rm n \geq Nn≥N , 则有 f ( n ) ≤ c g ( n ) \rm f(n) \leq cg(n)f(n)≤cg(n) ,
则称 g ( n ) \rm g(n)g(n) 是 f ( n ) \rm f(n)f(n) 的渐进上界 ;
符号化表示 :
∃ c > 0 ∃ N ∀ n ( n ≥ N ⇒ f ( n ) ≤ c g ( n ) ) \rm \exist c > 0 \ \exist N \ \forall n ( n \geq N \Rightarrow f(n) \leq cg(n) )∃c>0 ∃N ∀n(n≥N⇒f(n)≤cg(n))
存在 N \rm NN , 使得任何 n \rm nn 并且 n ≥ N \rm n \geq Nn≥N ,
∃ N ∀ n ( n ≥ N ) \exist N \ \forall n ( n \geq N )∃N ∀n(n≥N)
上述表述 , 表示 当 n \rm nn 充分大 ;
∃ N ∀ n ( n ≥ N ⇒ f ( n ) ≤ c g ( n ) ) \rm \exist N \ \forall n ( n \geq N \Rightarrow f(n) \leq cg(n) )∃N ∀n(n≥N⇒f(n)≤cg(n)) 整体的含义如下 ,
尽管 f ( n ) \rm f(n)f(n) 不一定小于等于 c g ( n ) \rm cg(n)cg(n) , 当 n \rm nn 充分大时 , 一定有 f ( n ) ≤ c g ( n ) \rm f(n) \leq cg(n)f(n)≤cg(n) , 这是一个趋势 ,
称 g ( n ) \rm g(n)g(n) 是 f ( n ) \rm f(n)f(n) 的渐进上界 ;
在渐近分析中 , 常数 c \rm cc 一般忽略不计 , 其大小是 2 , 3 2 , 32,3 或者几亿 都不重要 ;
二、大 O 记号
f ( n ) = O ( g ( n ) ) \rm f(n) = O(g(n))f(n)=O(g(n))
三、常用的渐进上界
多项式上界 : n c \rm n^cn
c
, 如 :
① n 2 = O ( n 2 ) \rm n^2 = O(n^2)n
2
=O(n
2
)
② 3 n 2 + 2 n + 1 = O ( n 2 ) \rm 3n^2 + 2n + 1 = O(n^2)3n
2
+2n+1=O(n
2
) , 忽略低阶项 , 系数项 ;
③ 4 n 3 + 2 n 2 + n + 3 = O ( n 3 ) \rm 4n^3 + 2n^2 + n + 3 = O(n^3)4n
3
+2n
2
+n+3=O(n
3
) , 忽略低阶项 , 系数项 ;
指数级上界 : 2 n c \rm 2^{n^c}2
n
c
, 如 :
① l o g n = O ( n x ) ( x > 0 ) \rm log n = O(n^x) \ (x > 0)logn=O(n
x
) (x>0)
大 O \rm OO 记号运算 :
O ( n ) + O ( n 2 ) = O ( n 2 ) \rm O(n) + O(n^2) = O(n^2)O(n)+O(n
2
)=O(n
2
) , 忽略低阶项 ;
渐进上界表示符号会 忽略系数影响 , 忽略低阶的项 ;
