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

第1讲简单的算法复杂性分析

算法复杂性算法复杂性（度）是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。算法分析的目的：设计算法——设计出复杂性尽可能低的算法选择算法——在多种算法中选择其中复杂性最低者算法分析（AlgorithmAnalysis）：对算法所需要的两种计算机资源——时间和空间进行估算时间复杂性（TimeComplexity）空间复杂性（SpaceComplexity）

算法效率的衡量方法同一算法，程序不同，运行时间不同写代码太费事，如果写出来才发现很慢…先写程序，直接观察结果不写程序，怎么知道运行时间？用“基本操作”数来衡量表达式很复杂怎么办？渐进表示不写程序，直接分析算法

sum:=0;fori:=1tondoforj:=1tondosum:=sum+a[i,j];基本操作：加法忽略循环变量i和j的改变时间共n2次基本操作时间复杂度为n2

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次基本操作那个算法好呢？算法（2）好，因为g(n)f(n)增长情况呢？n扩大10倍，f(n)扩大100倍，g(n)也扩大100倍两个算法的增长情况一样！渐进时间复杂度一样！

f(n)=n2和g(n)=n2/2增长情况一样如何表示“增长情况”？把f(n)和g(n)变成“渐进”形式，然后直接比较如何变成“渐进”形式？只保留最“大”项忽略系数例1：3n4+8n2+n+2?n4例2：2n+1+n100+5?2n(为什么n+1变成了n？)

回忆刚才的变换方法变换前后的增长情况一致需要先写出完整的式子至少知道最大项可是很多情况下无法知道最大项…不信？一个数n，如果它是奇数则变换到3n+1，否则变换到n/2给一个数n，不停的变换下去，经过几步变成1？你知道它的运行时间吗?!复杂度分析不是万能的！

渐进符号计算算法的时间复杂度时，往往不需要算出精确的结果，对于足够大的输入规模来说，我们只需要关心运行时间的增长量级，也就是研究算法的渐进效率。渐近意义下的记号：O、o、Ω、ω、Θ设f(n)和g(n)是定义在正数集上的正函数。

O的定义O(g(n))={f(n)|?n0,c0,s.t.?nn0,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(n))={f(n)|?c0,?n00,s.t.?nn0,0≤f(n)cg(n)}o记号表示的是一个非渐进的上界。记为：f(n)=o(g(n))，表示当n充分大时，函数f(n)的阶比g(n)低。

1Ω(g(n))={f(n)|?n0,c0,s.t.?nn0,0≤cg(n)≤f(n)}Ω记号表示的是函数的渐进下界。记为：f(n)=Ω(g(n))，表示f(n)的阶不低于g(n)的阶。Ω的定义2ω(g(n))={f(n)|?c0,?n00,s.t.?nn0,0≤cg(n)f(n)}ω记号表示的是一个非渐进的下界。记为：f(n)=ω(g(n))，表示当n充分大时，函数f(n)的阶比g(n)高。ω的定义

1Θ(g(n))={f(n)|?n0,c1,c20,s.t.?nn0,0≤c1g(n)≤f(n)≤c2g(n)}2Θ记号表示的是函数的渐进上界和下界。记为：f(n)=Θ(g(n))，表示f(n)与g(n)同阶。3f(n)=Θ(g(n))当且仅当f(n)=O(g(n))且f(n)=Ω(g(n))。Θ的定义

算法(渐进)时间复杂度,一般均表示为以下几种数量级的形式(n为问题的规模,c为一常量)：Ο(1)称为常数级Ο(logn)称为对数级Ο(n)称为线性级Ο(nc)称为多项式级Ο(cn)称为指数级Ο(n!)称为阶乘级

算法复杂性分类P复杂度01NP复杂度02