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

举报
韩曙亮 发表于 2022/01/11 02:03:15 2022/01/11
【摘要】 文章目录 一、渐进上界二、大 O 记号三、常用的渐进上界 一、渐进上界 g ...





一、渐进上界



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 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 > 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(nNf(n)cg(n))


存在 N \rm N N , 使得任何 n \rm n n 并且 n ≥ N \rm n \geq N nN ,

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

上述表述 , 表示 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(nNf(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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。