【计算理论】计算复杂性 ( 算法复杂度标记 | 渐进上界 | 大 O 记号 | 常用的渐进上界 )

一、渐进上界

g ( n ) \rm g(n) g(n) 是 f ( n ) \rm f(n) f(n) 的渐进上界 :

存在 c \rm c c , 并且存在 N \rm N N , 使得任何 n \rm n n , 并且 n ≥ N \rm n \geq N n≥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 N N , 使得任何 n \rm n n 并且 n ≥ N \rm n \geq N n≥N ,

∃ N   ∀ n ( n ≥ N ) \exist N \ \forall n ( n \geq N ) ∃N ∀n(n≥N)

上述表述 , 表示 当 n \rm n n 充分大 ;

∃ 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 n 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 \rm c c 一般忽略不计 , 其大小是 2 , 3 2 , 3 2,3 或者几亿 都不重要 ;

二、大 O 记号

f ( n ) = O ( g ( n ) ) \rm f(n) = O(g(n)) f(n)=O(g(n))

三、常用的渐进上界

多项式上界 : n c \rm n^c nc , 如 :

① n 2 = O ( n 2 ) \rm n^2 = O(n^2) n2=O(n2)

② 3 n 2 + 2 n + 1 = O ( n 2 ) \rm 3n^2 + 2n + 1 = O(n^2) 3n2+2n+1=O(n2) , 忽略低阶项 , 系数项 ;

③ 4 n 3 + 2 n 2 + n + 3 = O ( n 3 ) \rm 4n^3 + 2n^2 + n + 3 = O(n^3) 4n3+2n2+n+3=O(n3) , 忽略低阶项 , 系数项 ;

指数级上界 : 2 n c \rm 2^{n^c} 2nc , 如 :

① l o g n = O ( n x )   ( x > 0 ) \rm log n = O(n^x) \ (x > 0) logn=O(nx) (x>0)

大 O \rm O O 记号运算 :

O ( n ) + O ( n 2 ) = O ( n 2 ) \rm O(n) + O(n^2) = O(n^2) O(n)+O(n2)=O(n2) , 忽略低阶项 ;

渐进上界表示符号会 忽略系数影响 , 忽略低阶的项 ;