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

第1讲简单的算法复杂性分析,算法复杂性,算法复杂性（度）是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。,算法分析的目的：设计算法设计出复杂性尽可能低的算法选择算法在多种算法中选择其中复杂性最低者,算法分析（AlgorithmAnalysis）：对算法所需要的两种计算机资源时间和空间进行估算时间复杂性（TimeComplexity）空间复杂性（SpaceComplexity）,算法效率的衡量方法,先写程序，直接观察结果同一算法，程序不同，运行时间不同写代码太费事，如果写出来才发现很慢不写程序，直接分析算法不写程序，怎么知道运行时间？用“基本操作”数来衡量表达式很复杂怎么办？渐进表示,算法（1）分析,sum:=0;fori:=1tondoforj:=1tondosum:=sum+ai,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次基本操作那个算法好呢？算法（2）好，因为g(n)0,s.t.nn0,0f(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,0f(n)0,s.t.nn0,0cg(n)f(n)记号表示的是函数的渐进下界。记为：f(n)=(g(n)，表示f(n)的阶不低于g(n)的阶。,的定义(g(n)=f(n)|c0,n00,s.t.nn0,0cg(n)0,s.t.nn0,0c1g(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)称为线性级(nc)称为多项式级(cn)称为指数级(n!)称为阶乘级,P复杂度NP复杂度NPC复杂度,算法复杂性分类,简单算法的复杂性分析,对较复杂的算法计算算法的运行时间,经常从算法中选取一种对于所研究的问题来说是基本(或者说是主要)的原操作,以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。这个原操作,多数情况下是最深层次循环体内的语句中的原操作。例如：for(i=1;i=n;+i)for(j=1;j=n;+j)ci,j=0;for(k=0;k=n;+k)ci,j=ci,j+ai,k*bk,j;,最大连续和,给一串整数a1n，求出它和最大的子序列，即找出1=i=jmaxthenmax:=sum;end;时间复杂度如何分析？,算法一分析,当i和j一定的时候，内层循环执行j-i+1次总次数为应该如何计算？方法一：直接计算先计算里层求和号，得再加起来？好复杂自己做一做吧，得利用公式12+n2=O(n3)一般地，有1k+nk=O(nk+1),总次数为：完全的计算太麻烦能不能不动笔就知道渐进时间复杂度呢？何必非要计算出详细的公式再化简呢？里层求和计算出的结果是O(n-i)2)12+22+n2=O(n3)每步都化简！但是要保留外层需要的变量结论：算法一时间复杂度为O(n3)经验：一般只能支持nmaxthenmax:=sjsi-1;时间复杂度：预处理+主程序=O(n+n2)=O(n2).n=3000,算法三：分治,用一种完全不同的思路最大子序列的位置有三种可能完全处于序列的左半，即j=n/2跨越序列中间，即in/2j用递归的思路解决！设max(i,j)为序列aij的最大子序列那么,用递归的思路解决！设max(i,j)为序列aij的最大子序列设mid=(i+j)/2，即区间aij的中点最大的第一种序列为max(i,mid)最大的第二种序列为max(mid+1,j)问题：最大的第三种序列为？既然跨越中点，把序列aij划分为两部分aimid：最大序列用扫描法在n/2时间内找到一共只有mid-1=n/2种可能的序列，一一比较即可amid+1j：同理一共花费时间为j-i+1,算法三分析,如何分析时间复杂度呢？我们没有得到具体的T(n)的式子只有一个递推式子T(n)=2T(n/2)+n设时间复杂度的精确式子是T(n)第一、二种序列的计算时间是T(n/2)，因为序列长度缩小了一半第三种序列的计算时间是n计算出T(n)，就得到了时间复杂度怎样计算T(n)呢？,递归树分析,一般情形：T(n)=aT(n/b)+f(n)a,b为常数，f(n)为给定函数由递归树得结果为T(n)=f(n)+af(n/b)+a2f(n/b2)+aLf(n/bL)其中最后一项为递归边界，即n/bL=1，因此L=logbn,n/bL=1因此bL=n记L=logbn，称L为以b为底的n的对数对数的公式：logan+logam=loganmklogan=logank换底公式：logan/logbn=logba对数是一种增长很慢的函数log21000约为10log21000000约为20时间复杂度O(nlogn)和O(n2)相比是很大的提高！和O(n)在实际中相差并不是非常大,一般情形：T(n)=aT(n/b)+f(n)a,b为常数，f(n)为给定函数递归树得到的结果：T(n)=f(n)+af(n/b)+a2f(n/b2)+aLf(n/bL)其中L=logbn算法三的递推式：T(n)=2T(n/2)+na=2,b=2,f(n)=n对于第k项，有2kf(n/2k)=2k*n/2k=n一共有log2n项T(n)=n*log2n=O(nlogn).n=100,000底数2为什么没有了呢？换底公式：logan/logbn=logba=常数,算法四：贪心,算法二的实质是求出imaxthenmax:=sjmin_s;End;时间复杂度很明显：O(n).n=1,000,000,总结,