【计算理论】计算复杂性 ( 算法复杂度标记 | 渐进上界 | 大 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) , 忽略低阶项 ;
渐进上界表示符号会 忽略系数影响 , 忽略低阶的项 ;
文章来源: hanshuliang.blog.csdn.net,作者:韩曙亮,版权归原作者所有,如需转载,请联系作者。
原文链接:hanshuliang.blog.csdn.net/article/details/111030877
- 点赞
- 收藏
- 关注作者
评论(0)