简单的算法复杂度分析

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

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如果式子

3、再长一点，怎么办？比较两个算法算法（1）执行了f(n)=n2次基本操作算法（2）执行了g(n)=n2/2次基本操作那个算法好呢？算法（2）好，因为g(n)

4、+1变成了n？)复杂度分析不是万能的回忆刚才的变换方法变换前后的增长情况一致需要先写出完整的式子至少知道最大项可是很多情况下无法知道最大项…不信？一个数n，如果它是奇数则变换到3n+1，否则变换到n/2给一个数n，不停的变换下去，经过几步变成1？你知道它的运行时间吗?!复杂度分析不是万能的！渐进符号计算算法的时间复杂度时，往往不需要算出精确的结果，对于足够大的输入规模来说，我们只需要关心运行时间的增长量级，也就是研究算法的渐进效率。渐近意义下的记号：O、o、Ω、ω、Θ设f(n)和g(n)是定义在正数集上的正函数。O的定义O(g(

5、n))={f(n)

6、∃n0,c>0,s.t.∀n>n0,0≤f(n)≤cg(n)}O记号表示的是一个渐进上界，有时也被非正式地用来描述渐进上确界。记为：f(n)=O(g(n))，表示f(n)的阶不高于g(n)的阶。根据O的定义，容易证明它有如下运算规则：(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(

7、n))={f(n)

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

9、∃n0,c>0,s.t.∀n>n0,0≤cg(n)≤f(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、为：f(n)=ω(g(n))，表示当n充分大时，函数f(n)的阶比g(n)高。Θ的定义Θ(g(n))={f(n)

12、∃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))且f(n)=Ω(g(n))。算法(渐进)时间复杂度,一般均表示为以下几种数量级的形式(n为问题的规模,c为一常量)：Ο(1)称为常数级Ο(logn)称为对数级Ο(n)称为线性级Ο(n

13、c)称为多项式级Ο(cn)称为指数级Ο(n!)称为阶乘级P复杂度NP复杂度NPC复杂度算法复杂性分类简单算法的复杂性分析对较复杂的算法计算算法的运行时间,经常从算法中选取一种对于所研究的问题来说是基本(或者说是主要)的原操作,以该基本操作在算法中重复执行的次数作