算法设计与分析(1)_第1页
算法设计与分析(1)_第2页
算法设计与分析(1)_第3页
算法设计与分析(1)_第4页
算法设计与分析(1)_第5页
已阅读5页，还剩9页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、 1.4 算法复杂性分析 算法复杂性是算法运行所需要的计算机资源的量， 需要时间资源的量称为时间复杂性，需要的空间资源的 量称为空间复杂性。这个量应该只依赖于算法要解的问 题的规模、算法的输入和算法本身的函数。如果分别用 N、I和A表示算法要解问题的规模、算法的输入和算法 本身，而且用C表示复杂性，那么，应该有C=F(N,I,A。 一般把时间复杂性和空间复杂性分开，并分别用T和S来 表示，则有： T=T(N,I和S=S(N,I 。 （通常，让A隐含在复杂性函数名当中） 26 1.4 算法复杂性分析 最坏情况下的时间复杂性： Tmax (N = max T ( N , I = max å

2、; t i ei ( N , I = å t i ei ( N , I * = T ( N , I * I ÎDN I ÎDN i =1 i =1 k k 最好情况下的时间复杂性： Tmin (N = min T ( N , I = min å ti ei ( N , I = å t i ei ( N , I = T ( N , I I ÎD I ÎDN N k k i =1 i =1 平均情况下的时间复杂性： Tavg(N = I ÎDN å P( I T ( N , I = å P( I &

3、#229; t e ( N , I I ÎDN i =1 i i k 其中DN是规模为N的合法输入的集合；I*是DN中使T(N, I* 达到Tmax(N的合法输入； I 是中使T(N, I 达到Tmin(N的合法 输入；而P(I是在算法的应用中出现输入I的概率。 27 1.4 算法复杂性分析 算法复杂性在渐近意义下的阶： 渐近意义下的记号：O、 、 、o 设f(N和g(N是定义在正数集上的正函数。 O的定义：如果存在正的常数C和自然数N0，使得当N³N0时有 f(N£Cg(N，则称函数f(N当N充分大时上有界，且g(N是它的一 个上界，记为f(N=O(g(N。即f

4、(N的阶不高于g(N的阶。 根据O的定义，容易证明它有如下运算规则： (1O(f+O(g=O(max(f,g； (2O(f+O(g=O(f+g； (3O(fO(g=O(fg； (4如果g(N=O(f(N，则O(f+O(g=O(f； (5O(Cf(N=O(f(N，其中C是一个正的常数； (6f=O(f。 28 1.4 算法复杂性分析 的定义：如果存在正的常数C和自然数N0，使得当N³N0时 有f(N³Cg(N，则称函数f(N当N充分大时下有界，且g(N是它 的一个下界，记为f(N= (g(N。即f(N的阶不低于g(N的阶。 的定义：定义f(N= (g(N当且仅当f(N=O(g(N且 f(N= (g(N。此时称f(N与g(N同阶。 o的定义：对于任意给定的0，都存在正整数N0，使得 当N³N0时有f(N/Cg(N£

人人文库> 全部分类> 教育资料 > 辅导培训

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论