1、第第1 1讲讲 简单的算法复杂性分析简单的算法复杂性分析算法复杂性算法复杂性算法复杂性（算法复杂性（度度）是）是算法运行所需要的计算机资源的量算法运行所需要的计算机资源的量，需要需要时间资源的量称为时间资源的量称为时间复杂性时间复杂性，需要的空间资源需要的空间资源的量的量称为称为空间复杂性空间复杂性。算法分析的目的：算法分析的目的：设计算法设计算法设计出复杂性尽可能低的设计出复杂性尽可能低的算法算法 选择算法选择算法在多种算法中选择其中复杂性最低者在多种算法中选择其中复杂性最低者算法分析（算法分析（Algorithm Analysis）：对算法所需要）：对算法所需要的两种计算机资源的两种计算机
2、资源时间和空间进行估算时间和空间进行估算 时间复杂性（时间复杂性（Time Complexity）空间复杂性（空间复杂性（Space Complexity）算法效率的衡量方法算法效率的衡量方法p先写程序，直接观察结果先写程序，直接观察结果n同一算法，程序不同，运行时间不同同一算法，程序不同，运行时间不同n写代码太费事，如果写出来才发现很慢写代码太费事，如果写出来才发现很慢p不写程序，直接分析算法不写程序，直接分析算法n不不写程序，怎么知道运行时间？写程序，怎么知道运行时间？u用用“基本操作基本操作”数来衡量数来衡量n表达式很复杂怎么办？表达式很复杂怎么办？u渐进表示渐进表示算法（算法（1）分析
3、）分析sum:=0;for i:=1 to n do for j:=1 to n do sum:=sum+ai,j;p基本操作：加法基本操作：加法p忽略循环变量忽略循环变量i和和j的改变时间的改变时间p共共n2次基本操作次基本操作p时间复杂度为时间复杂度为n2算法（算法（2）分析）分析sum:=0;for i:=1 to n do begin fact:=1;for j:=1 to i do fact:=fact*i;sum:=sum+fact;endp 第第i次循环执行了次循环执行了i个操作个操作p 总时间复杂度为总时间复杂度为1+2+3+n=n(n+1)/2p 如果式子再长一点，怎么办？如
4、果式子再长一点，怎么办？比较两个算法比较两个算法p算法（算法（1）执行了）执行了f(n)=n2次基本操作次基本操作p算法（算法（2）执行了）执行了g(n)=n2/2次基本操作次基本操作p那个算法好呢？那个算法好呢？n算法（算法（2）好，因为）好，因为g(n)0,0,s.t.s.t.nn nn0 0,0,0 f(n)f(n)cg(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)(
5、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)po的定义的定义o(g(n)=f(n)|c0,n c0,n0 00,0,s.t.s.t.nn nn0 0,0,0 f(n)cg(n)f(n)0,c 0,s.t.s.t.nn nn0 0,0,0 cg(n)cg(n)f(n)f(n)记号表示的是函数的渐进下界。记为：f(n)=(g(n)，表示f(n)的阶不低于g(n)的阶。p的定义的定义(g(n)=f(n)|c 0,n c 0,n0 0 0,0,s.t.s.t.nn nn0 0,
6、0,0 cg(n)cg(n)0,0,s.t.s.t.nn nn0 0,0,0 c c1 1g(n)g(n)f(n)f(n)c c2 2g(n)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)称为常数级称为常数级(logn)称为对数级称为对数级(n)称为线性级称为线性级(nc)称为多项式级称为多项式级(
7、cn)称为指数级称为指数级(n!)称为阶乘级称为阶乘级pP复杂度复杂度pNP复杂度复杂度pNPC复杂度复杂度算法复杂性分类算法复杂性分类简单算法的复杂性分析简单算法的复杂性分析对较复杂的算法计算算法的运行时间,经常从算法中选取一种对于所研究的问题来说是基本基本(或者说是主要或者说是主要)的原操作,以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。这个原操作,多数情况下是最深层次循环体内的语句中的原操作。例如：例如：for(for(i i=1;i=1;i=n;+=n;+i i)for(j=1;j for(j=1;j=n;+j)=n;+j)c ci,ji,j=0;=0;for(k=0;
8、kfor(k=0;k=n;+k)=n;+k)cci,ji,j=c=ci,ji,j+a+ai,ki,k*bbk,jk,j;最大连续和最大连续和p给一串整数给一串整数a1n，求出它和最大的子序列，求出它和最大的子序列，即找出即找出1=i=j max then max:=sum;end;p 时间复杂度如何分析？时间复杂度如何分析？算法一分析算法一分析p当当i和和j一定的时候，内层循环执行一定的时候，内层循环执行j-i+1次次p总次数为总次数为p应该如何计算？应该如何计算？p方法一：直接计算方法一：直接计算n 先计算里层求和号，得先计算里层求和号，得n 再加起来？好复杂再加起来？好复杂n 自己做一做吧
9、，得利用公式自己做一做吧，得利用公式12+n2=O(n3)n 一般地，有一般地，有1k+nk=O(nk+1)1(1)nnij iji 11(1)(2)2ninini p总次数为：总次数为：n 完全的计算太麻烦完全的计算太麻烦n 能不能不动笔就知道渐进时间复杂度呢？能不能不动笔就知道渐进时间复杂度呢？p何必非要计算出详细的公式再化简呢？何必非要计算出详细的公式再化简呢？n 里层求和计算出的结果是里层求和计算出的结果是O(n-i)2)n 12+22+n2=O(n3)n 每步都化简！但是要保留外层需要的变量每步都化简！但是要保留外层需要的变量p结论：算法一时间复杂度为结论：算法一时间复杂度为O(n3
10、)p经验：一般只能支持经验：一般只能支持 n max then max:=sj si-1;p 时间复杂度：预处理时间复杂度：预处理+主程序主程序=O(n+n2)=O(n2).n=3000算法三：分治算法三：分治p用一种完全不同的思路用一种完全不同的思路p最大子序列的位置有三种可能最大子序列的位置有三种可能n完全处于序列的左半，即完全处于序列的左半，即j=n/2n跨越序列中间，即跨越序列中间，即in/2jp用递归的思路解决！用递归的思路解决！n设设max(i,j)为序列为序列aij的最大子序列的最大子序列u那么那么p用递归的思路解决！用递归的思路解决！n 设设max(i,j)为序列为序列aij的
11、最大子序列的最大子序列n 设设mid=(i+j)/2，即区间，即区间aij的中点的中点u最大的第一种序列为最大的第一种序列为max(i,mid)u最大的第二种序列为最大的第二种序列为max(mid+1,j)p问题：最大的第三种序列为？问题：最大的第三种序列为？n 既然跨越中点，把序列既然跨越中点，把序列aij划分为两部分划分为两部分uaimid：最大序列用扫描法在：最大序列用扫描法在n/2时间内找到时间内找到 一共只有mid-1=n/2种可能的序列，一一比较即可uamid+1j：同理：同理u一共花费时间为一共花费时间为j-i+1算法三分析算法三分析p如何分析时间复杂度呢？如何分析时间复杂度呢？
12、n我们没有得到具体的我们没有得到具体的T(n)的式子的式子n只有一个递推式子只有一个递推式子T(n)=2T(n/2)+nu设时间复杂度的精确式子是设时间复杂度的精确式子是T(n)u第一、二种序列的计算时间是第一、二种序列的计算时间是T(n/2)，因为序列长度缩，因为序列长度缩小了一半小了一半u第三种序列的计算时间是第三种序列的计算时间是nn计算出计算出T(n)，就得到了时间复杂度，就得到了时间复杂度u怎样计算怎样计算T(n)呢？呢？递归树分析递归树分析p 一般情形：一般情形：T(n)=aT(n/b)+f(n)n a,b为常数，为常数，f(n)为给定函数为给定函数n 由递归树得结果为由递归树得结
13、果为T(n)=f(n)+af(n/b)+a2f(n/b2)+aLf(n/bL)n 其中最后一项为递归边界，即其中最后一项为递归边界，即n/bL=1，因此，因此L=logbn aLf(1)a3f(n/b3)a2f(n/b2)af(n/b)f(n)a a f(n)f(n/b)f(n/b)f(n/b)f(n/b)f(n/b2)f(n/b2)f(n/b2)f(n/b2)f(n/b3)f(1)pn/bL=1n 因此因此bL=nn 记记L=logbn，称，称L为以为以b为底的为底的n的对数的对数n 对数的公式：对数的公式：ulogan+logam=loganmuklogan=loganku换底公式：换底公
14、式：logan/logbn=logban 对数是一种增长很慢的函数对数是一种增长很慢的函数ulog21000 约为约为 10ulog21000000 约为约为20n 时间复杂度时间复杂度O(nlogn)和和O(n2)相比是很大的提高！相比是很大的提高！u和和O(n)在实际中相差并不是非常大在实际中相差并不是非常大p 一般情形：一般情形：T(n)=aT(n/b)+f(n)n a,b为常数，为常数，f(n)为给定函数为给定函数p 递归树得到的结果：递归树得到的结果：n T(n)=f(n)+af(n/b)+a2f(n/b2)+aLf(n/bL)n 其中其中L=logbnp 算法三的递推式：算法三的递
15、推式：T(n)=2T(n/2)+nn a=2,b=2,f(n)=nn 对于第对于第k项，有项，有2kf(n/2k)=2k*n/2k=nn 一共有一共有log2n项项n T(n)=n*log2n=O(nlogn).n=100,000p 底数底数2为什么没有了呢？为什么没有了呢？n 换底公式：换底公式：logan/logbn=logba=常数常数算法四：贪心算法四：贪心p算法二的实质是求出算法二的实质是求出i=j,让让sj-si-1最大最大n 对于给定的对于给定的j，能否直接找到在，能否直接找到在j之前的最小之前的最小s值呢？值呢？n 从小到大扫描从小到大扫描juj=1时，只有一个合法的时，只有一个合法的i，即，即i=1,s1-1=0u如果如果sj变大，则最小的变大，则最小的s值和上次一样值和上次一样u如果如果sj再创新低，应该让再创新低，应该让sj作为今后的最优作为今后的最优s值值min_s:=0;For j:=1 to n do begin if sj max then max:=sj min_s;End;p 时间复杂度很明显：时间复杂度很明显：O(n).n=1,000,000总结总结算法时间复杂度分析方法枚举O(n3)分层求和优化枚举O(n2)明显分治O(nlogn)递归树扫描O(n)明显
