简单的算法复杂度分析.ppt

简单的算法复杂度分析.ppt

ID:51998765

大小:294.50 KB

页数:30页

时间:2020-03-27

简单的算法复杂度分析.ppt_第1页
简单的算法复杂度分析.ppt_第2页
简单的算法复杂度分析.ppt_第3页
简单的算法复杂度分析.ppt_第4页
简单的算法复杂度分析.ppt_第5页
资源描述:

《简单的算法复杂度分析.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第1讲简单的算法复杂性分析算法复杂性算法复杂性(度)是算法运行所需要的计算机资源的量,需要时间资源的量称为时间复杂性,需要的空间资源的量称为空间复杂性。算法分析的目的:设计算法——设计出复杂性尽可能低的算法选择算法——在多种算法中选择其中复杂性最低者算法分析(AlgorithmAnalysis):对算法所需要的两种计算机资源——时间和空间进行估算时间复杂性(TimeComplexity)空间复杂性(SpaceComplexity)算法效率的衡量方法先写程序,直接观察结果同一算法,程序不同,运行时间不同写代码太费事,如果写出来才发现很慢…不写程序,直接分析算法不写程序,怎么知道运行时间?

2、用“基本操作”数来衡量表达式很复杂怎么办?渐进表示算法(1)分析sum:=0;fori:=1tondoforj:=1tondosum:=sum+a[i,j];基本操作:加法忽略循环变量i和j的改变时间共n2次基本操作时间复杂度为n2算法(2)分析sum:=0;fori:=1tondobeginfact:=1;forj:=1toidofact:=fact*i;sum:=sum+fact;end第i次循环执行了i个操作总时间复杂度为1+2+3+…+n=n(n+1)/2如果式子再长一点,怎么办?比较两个算法算法(1)执行了f(n)=n2次基本操作算法(2)执行了g(n)=n2/2次基本操作那

3、个算法好呢?算法(2)好,因为g(n)

4、到3n+1,否则变换到n/2给一个数n,不停的变换下去,经过几步变成1?你知道它的运行时间吗?!复杂度分析不是万能的!渐进符号计算算法的时间复杂度时,往往不需要算出精确的结果,对于足够大的输入规模来说,我们只需要关心运行时间的增长量级,也就是研究算法的渐进效率。渐近意义下的记号:O、o、Ω、ω、Θ设f(n)和g(n)是定义在正数集上的正函数。O的定义O(g(n))={f(n)

5、∃n0,c>0,s.t.∀n>n0,0≤f(n)≤cg(n)}O记号表示的是一个渐进上界,有时也被非正式地用来描述渐进上确界。记为:f(n)=O(g(n)),表示f(n)的阶不高于g(n)的阶。根据O的定义,容易

6、证明它有如下运算规则:(1)O(f)+O(g)=O(max(f,g))(2)O(f)+O(g)=O(f+g)(3)O(f)O(g)=O(fg)(4)如果g(n)=O(f(n)),则O(f)+O(g)=O(f)(5)O(Cf(n))=O(f(n)),其中C是一个正的常数(6)f=O(f)o的定义o(g(n))={f(n)

7、∀c>0,∃n0>0,s.t.∀n>n0,0≤f(n)

8、∃n0,c>0,s.t.∀n>n0,0≤cg(n)≤f

9、(n)}Ω记号表示的是函数的渐进下界。记为:f(n)=Ω(g(n)),表示f(n)的阶不低于g(n)的阶。ω的定义ω(g(n))={f(n)

10、∀c>0,∃n0>0,s.t.∀n>n0,0≤cg(n)

11、∃n0,c1,c2>0,s.t.∀n>n0,0≤c1g(n)≤f(n)≤c2g(n)}Θ记号表示的是函数的渐进上界和下界。记为:f(n)=Θ(g(n)),表示f(n)与g(n)同阶。f(n)=Θ(g(n))当且仅当f(n)=O(g(n

12、))且f(n)=Ω(g(n))。算法(渐进)时间复杂度,一般均表示为以下几种数量级的形式(n为问题的规模,c为一常量):Ο(1)称为常数级Ο(logn)称为对数级Ο(n)称为线性级Ο(nc)称为多项式级Ο(cn)称为指数级Ο(n!)称为阶乘级P复杂度NP复杂度NPC复杂度算法复杂性分类简单算法的复杂性分析对较复杂的算法计算算法的运行时间,经常从算法中选取一种对于所研究的问题来说是基本(或者说是主要)的原操作,以该基本操作在算法中重复执行的次数作

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。