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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第,1,讲 简单,的,算法复杂性分析,算法复杂性,算法复杂性（,度,）是,算法运行所需要的计算机资源的量,，需要,时间资源的量称为,时间复杂性,，,需要的空间资源,的量,称为,空间复杂性,。,算法分析的目的：,设计算法,设计出复杂性尽可能低的,算法,选择算法,在多种算法中选择其中复杂性最低者,算法分析（,Algorithm Analysis,）：对算法所需要的两种计算机资源,时间和空间进行估算,时间复杂性（,Time Complexity,）,空间复杂性（,Space Complexity,）,算法效率的衡量方法,先写程序，直接观察结果,同一算法，程序不同，运行时间不同,写代码太费事，如果写出来才发现很慢,不写程序，直接分析算法,不,写程序，怎么知道运行时间？,用“基本操作”数来衡量,表达式很复杂怎么办？,渐进表示,算法,（,1,）分析,sum:=0;,for i:=1 to n do,for j:=1 to n do,sum:=sum+ai,j;,基本操作：加法,忽略循环变量,i,和,j,的改变时间,共,n,2,次基本操作,时间复杂度为,n,2,算法,（,2,）分析,sum:=0;,for i:=1 to n do begin,fact:=1;,for j:=1 to i do,fact:=fact*i;,sum:=sum+fact;,end,第,i,次循环执行了,i,个操作,总时间复杂度为,1+2+3+n=n(n+1)/2,如果式子再长一点，怎么办？,比较两个算法,算法（,1,）执行了,f(n)=n,2,次基本操作,算法（,2,）执行了,g(n)=n,2,/2,次基本操作,那个算法好呢？,算法（,2,）好，因为,g(n)0,s.t.nn,0,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,n,0,0,s.t.nn,0,0,f(n)0,s.t.nn,0,0,cg(n),f(n),记号表示的是函数的渐进下界。记为：,f(n)=,(g(n),，表示,f(n),的阶不低于,g(n),的阶。,的定义,(g(n)=f(n)|,c 0,n,0,0,s.t.nn,0,0,cg(n)0,s.t.nn,0,0,c,1,g(n),f(n),c,2,g(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),称为常数级,(log,n,),称为对数级,(n,),称为线性级,(n,c,),称为多项式级,(c,n,),称为指数级,(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=j max then max:=sum;,end;,时间复杂度如何分析？,算法一分析,当,i,和,j,一定的时候，内层循环执行,j-i+1,次,总次数为,应该如何计算？,方法一：直接计算,先计算里层求和号，得,再加起来？好复杂,自己做一做吧，得利用公式,1,2,+n,2,=O(n,3,),一般地，有,1,k,+n,k,=O(n,k+1,),总次数为：,完全的计算太麻烦,能不能不动笔就知道渐进时间复杂度呢？,何必非要计算出详细的公式再化简呢？,里层求和计算出的结果是,O(n-i),2,),1,2,+2,2,+n,2,=O(n,3,),每步都化简！但是要保留外层需要的变量,结论：算法一时间复杂度为,O(n,3,),经验：一般只能支持,n max then,max:=sj si-1;,时间复杂度：预处理,+,主程序,=O(n+n,2,)=O(n,2,).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)+a,2,f(n/b,2,)+a,L,f(n/b,L,),其中最后一项为递归边界，即,n/b,L,=1,，因此,L=log,b,n,n/b,L,=1,因此,b,L,=n,记,L=log,b,n,，称,L,为以,b,为底的,n,的对数,对数的公式：,log,a,n+log,a,m=log,a,nm,klog,a,n=log,a,n,k,换底公式：,log,a,n/log,b,n=log,b,a,对数是一种增长很慢的函数,log,2,1000,约为,10,log,2,1000000,约为,20,时间复杂度,O(nlogn),和,O(n,2,),相比是很大的提高！,和,O(n),在实际中相差并不是非常大,一般情形：,T(n)=aT(n/b)+f(n),a,b,为常数，,f(n),为给定函数,递归树得到的结果：,T(n)=f(n)+af(n/b)+a,2,f(n/b,2,)+a,L,f(n/b,L,),其中,L=log,b,n,算法三的递推式：,T(n)=2T(n/2)+n,a=2,b=2,f(n)=n,对于第,k,项，有,2,k,f(n/2,k,)=2,k*,n/2,k,=n,一共有,log,2,n,项,T(n)=n*log,2,n=O(nlogn).n=100,000,底数,2,为什么没有了呢？,换底公式：,log,a,n/log,b,n=log,b,a=,常数,算法,四：,贪心,算法二的实质是求出,i=j,让,sj-si-1,最大,对于给定的,j,，能否直接找到在,j,之前的最小,s,值呢？,从小到大扫描,j,j=1,时，只有一个合法的,i,，即,i=1,s1-1=0,如果,sj,变大，则最小的,s,值和上次一样,如果,sj,再创新低，应该让,sj,作为今后的最优,s,值,min_s:=0;,For j:=1 to n do begin,if sj max then,max:=sj min_s;,End;,时间复杂度很明显：,O(n).n=1,000,000,总结,算法,时间复杂度,分析方法,枚举,O(n,3,),分层求和,优化枚举,O(n,2,),明显,分治,O(nlogn),递归树,扫描,O(n),明显,