复杂性分析及简单枚举_第1页
复杂性分析及简单枚举_第2页
复杂性分析及简单枚举_第3页
复杂性分析及简单枚举_第4页
复杂性分析及简单枚举_第5页
已阅读5页,还剩32页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、复杂性分析及简单枚举算法,什么是算法,做什么事情,都有一个解决问题基本方法。写程序也是一样,我们在写程序之前,事先需要有一个思路,然后根据自己的思路,用程序设计语言来描述出来,这个思路,我们称为算法。 例 NN的矩阵的每一个元素都是整数,求这个矩阵中所有数的和,我们可以设计一个统计变量,用两重循环枚举每一个数,然后将数值统计到统计变量中即可。因此可设计算法如下。,Sum:=0; 未统计时,统计变量清0 FOR i :=1 TO n DO FOR j :1 TO n DO Sum := Sum + ai,j; 统计,设计算法的基本目标,1)正确性(correctness)。算法应当满足具体问题的

2、需求。包括给定的输入数据,得到正确的输出结果。 2)可读性(readability)。算法要求能便于人的阅读与交流,这样有助于交流、调试和修改。 3)健壮性(robustness)。要考虑输入数据非法时,算法也能适当地作出反应或进行处理,而不会产生莫明其妙的输出结果。例如,给出三角形的三条边长,求三角形的面积。要考虑当输入的数据不能构成三角形的情形。 4)高效率(efficiency)。算法设计出来后,必须考虑在运行时间和存储空间方面的需求。算法的效率通常是指的算法执行时间。算法必须能在有限步终止,并且在可终止的前提下,算法的效率应尽可能的高。对于同一个问题如果有多个算法可以解决,执行时间短的

3、算法效率高。存储量需求指算法执行过程中所需要的最大存储空间,这两者都与问题的规模有关。例如,要对n个数进行排序,当n越大时,所需的空间和运行的时间跟n有关。,时空分析时间复杂度,时间复杂度又称计算复杂度,是指执行程序的计算工作量。同一问题,采用不同的算法,程序的计算工和量是不一样的。衡量一个算法的时间复杂度,可以采用两种方法:执行时间和执行运算次数。,执行时间,指在计算机上运行程序从开始到结束所花费的时间。执行时间与计算机配置有关,配置越高的机器,运算速度越快,执行时间越少,反之越多。因计算机配置差异太大,这种方法可取性不高。,执行运算次数是根据程序中执行指令条数和语句条数来度量的,它大致等于

4、计算机执行一种简单操作所需时间与算法中简单操作次数的乘积。这种方法不以计算机的配置为依据,而以算法中的操作次数总耗时为依据,耗时越少,执行时间越快;耗时越多,执行时间越慢。这种方法已经被作为衡量时间复杂度的最有效方法。,下面通过一个例子来分析简单操作次数。 从键盘上读入100个正整数,输出其中最大的数。,Max:=0; For i:=1 to 100 do begin read(tmp); if tmpmax then max:=tmp; end; writeln(max);,程序执行次数,所以,该程序的简单操作数在最坏情况下为201次。,在NOI的各类比赛和网上的题库中,每道题在时间上都有详

5、细的要求,比如说有些题要求在1秒钟内出答案,有些题要求在5秒钟内出答案,那么,如何用运算次数估算运行时间呢?运算的快慢与计算机硬件配置有很大的关系,配置越高,运算越快,在1秒钟内的运算次数就越多,反之越少。而且1秒钟能进行的运算次数也只能粗略地估算。一般来说,根据CCF发布在官肉上的现用评测机配置来看,在1秒钟的时限内可以运行1亿的操作次数。为了在给定的时间内跑出题目中的所有数据,在衡量时间复杂度时,应着重考虑输入数据。,输入数据包括输入规模和输入情况。用n表示输入规模,当用选择排序法对n个数进排序时,在忽略耗时较少的赋值、交换等操作语句情况下,对应的操作次数如下表:,不同数据规模对应的操作次

6、数,选择排序的时间复杂度为n*n,从表中可以看出,当n成10倍数增长时,操作次数成百倍增长。当某些算法是指数级别时,输入数据的规模稍大一点,就极易超时。所以在编程时,尤其要考虑输入数据的规模。,从输入文件中读入n(n=100)个整数,输出第一次出现数字1的位置。,For i:=1 to n do begin readln(num); if num=1 then break; end; Write(i);,输入数据,当第一个数字为1时,操作次数仅有1次;当第n个数字才为1时,操作次数则有n次,两种情况下操作次数相差近n倍。所以同一个程序,当输入数据情况不一样时,操作次数可能会相差很大。因此在计算

7、时间复杂度时,需要考虑输入数据的不同情况。但是,输入情况非常多,每种情况都计算时间复杂度的话,是不现实的。比如本题,数字1出现的位置有n种情况,对应的操作次数也有n种情况。我们用O(n)表示此算法的时间复杂度,n为问题的规模;当语句执行次数为常数时,我们用O(1)表示时间复杂度。根据现在NOI中各类竞赛和各大题库中的题目,对于每组输入数据,都有测试时间限制,我们可以根据输入数据的最坏情况来设计时间复杂度。最坏情况下的时间复杂度称最坏时间复杂度。,时间复杂度的等级,时间复杂度排序 O(1) O(loglogn) O(logn) O(n) O(n) O(nloglogn) O(nlogn) O(n

8、2) O(n2) O(n) O(2) O(n!) O(n),显然,时间复杂度为指数阶O(n2) 的算法效率极低,当n值稍大时就无法应用。 为了降低一个程序的时间复杂度,提高时间效率,我们应精心设计算法,对程序细节进行优化。,空间复杂度,与时间复杂度类似,空间复杂度是指一个程序在计算机中执行时所需要的存储空间大小的一个度量,包括程序本身、程序的输入输出相关的全局变量和在运行过程中临时占用的存储空间。 程序本身所占用的空间与程序的长短成正比,要压缩这方面的空间,应使用较短程序的算法,如递归算法。 程序输入输出相关的全局变量占用的空间随题目而异,在题目给出输入输出规模后,就要分配相应的存储单元。 在

9、运行过程中临时占用的存储空间与算法有关,不同的算法有不同的函数参数和局部变量,占用的空间也不一样。 在考虑一个算法的空间复杂度时,一般只需考虑根据题意设定的全局变量的大小和在运行过程中临时战胜的存储空间。,从NOIP2008开始,CCF为联赛规定了内在限制,规定其中静态内存和动态内存占用的空间。静态内存指程序初始时设定的全局变量占用的空间,动态内存指执行程序时形参变量分配的存储空间和函数体或过程体中定义的局部变量等占用的空间。 全局变量占用的空间为静态内存,可以详细地计算出来。计算全局变量占用的空间时,要根据所用的变量类型、数组长度来计算。,如在程序中定义了如下全局变量: f:array1.1

10、000,1.1000 of longint; ch:array1.1000 of string; d:array1.1000 of double;,它们占用的空间为: f数组:1000*1000*4byte(字节,一个longint占用4个字节) ch数组:1000*256byte(字节,一个string占用256个字节) d数组:1000*8byte(字节,一个double占用4个字节),占用的静态空间为: f数组+ch数组+d数组4264000Bye4MB,例1判断下列式子的时间复杂度,(1) 3n4+8n2+n+2 (2) 2n+1+n100+5 (3) 12+n2 (4) 1k+nk

11、(5) (6),解答,O(n4)。因为n4的阶比n2高。 O(2n+1)。因为2n+1的增长速度远大于n100。n100是多项式级别,而2n+1是指数级别,另外也可以从导数的角度来看。n100的101阶导数等于0,而2n+1的101阶导数等于C(n+1,100)2n-100。 O(n3)。12+22+n2=n(n+1)(2n+1)/6O(n3) O(nk+1)。类似(3)。 O(n2)。因为该式子相当于两重循环,外循环i从1n变化,内循环j从in变化。 令i=n-i+1,i从1 n,则i也是从1 n,原式与 等价,将该式拆开 ,前一个为O(n3),后一个 为O(n2),因此复杂度为O(n3)。

12、,例2,输入n个数,求这n个数的最大数和最小数。 算法设计如下: min:=MAXINT; max:=-MAXINT; 初始化最大最小值 FOR i:=1 TO n DO Begin READ(x); IF xmax THEN max:=x; end; 上述程序中,循环内部包含了三个语句,这三个语句都是原操作,总共执行了n次,因此,该算法的时间复杂度为,O(n)。,例3,给出n个数,存储在数组data中,要求将这n个数按从小到大的顺序排列到data中。我们可以用简单选择排序来解决,第一次从所有的数中选择一个最小的数,放在数组的第一个位置,接着从剩下的数选择最小的数放到第二个位置,.,以此类推,

13、做n-1次选择,就将n个数排好了序。因此我们可以写出如下算法: FOR i:=1 TO n-1 DO 做n-1次选择 FOR j:=i+1 TO n DO 从i后面的所有数中选择最小的数 IF dataidataj THEN 交换datai和dataj; 将小数放在前面去 原语句为“IF dataidataj THEN 交换datai和dataj”,显然该语句共执行了(n-1)+(n-2)+1=n*(n-1)/2=n2/2-n/2次。 由于n2 比n增长更快,因此,该算法的时间复杂度为O(n2),简单枚举算法(穷举法),枚举法是基于计算机的特点来解决问题的思维方法。竞赛题目就是写一个能在允许时

14、间内解出的程序而无须更多地考虑是否存在一个更快的算法。枚举法的特点是算法简单,容易编程与调试,所以枚举法应该是选手们第一个能够想到的算法。但枚举法也有不足,即运行时会花费很长时间。在解题的过程中,选手们应尽可能将明显的不符合条件的情况排除在外,以便提高运行速度,减少运行时间。,简单枚举法,所谓枚举法,是程序设计中常见的一种算法,它利用计算机运算速度快精度高的特点,对问题的所有可能情况(可能解),一个不漏地(最好也不重复)依次进行检查,从中找出符合要求的解(合理解)。枚举法通常采用(多重)循环来实现。一般思路: 对命题建立正确的数学模型; 根据命题确定的数学模型中各变量的变化范围(即可能解的范围

15、); 利用循环语句、条件判断语句逐步求解或证明; 枚举法的特点是算法简单,但有时运算量大。对于可能确定解的值域又一时找不到其他更好的算法时可以采用枚举法。,虽然枚举法本质上属于搜索策略,但是它与回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件: 可预先确定每个状态的元素个数n; 状态元素a1,a2,an的可能值为一个连续的值域。 设 ai1状态元素ai的最小值;aik状态元素ai的最大值(1in),即a11a1a1k,a21a2a2k, ai1aiaik,an1anank for a1a11 to a1k do for a2a21 to a2k do for aiai1 to aik

16、do for anan1 to ank do if 状态(a1,ai,an)满足检验条件 then 输出问题的解;,枚举法的优点: 由于枚举算法一般是现实生活中问题的“直译”,因此比较直观,易于理解; 由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上,所以算法的正确性比较容易证明。 枚举法的缺点: 枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价,因此效率比较低。,枚举法优缺点,示例,求满足表达式A+B=C的所有整数解,其中A,B,C为1100之间的整数。 分析:本题非常简单,即枚举所有情况,符合表达式即可。 算法如下: for A := 1 to 100 do for B

17、:= 1 to 100 do for C := 1 to 100 do if A + B = C then Writeln(A, +, B, =, C);,显然可以修改如下: for A := 1 to 100 do for B := 1 to 100 do C := A+B if (C=1)then Writeln(A, +, B, =, C);,例 1,古希腊人认为因子的和等于它本身的数是一个完全数(自身因子除外),例如28的因子是1、2、4、7、14,且1+2+4+7+14=28,则28是一个完全数,编写一个程序求2至1000以内的所有完全数。,分析与解答 由题目的已知条件可得,完全数的

18、搜索范围是从2到1000,完全数必须满足的条件是因子的和等于该数的本身,由此我们发现本题的关键就是确定该数的各个因子,如何找出这些因子?根据已有的数学知识,除了该数本身外(从题目中的已知条件可知),能除尽该数的所有数都是该数的因子,因此可以利用循环来求解,最后将求出的因子相加并与该数进行比较。如果相等,则该数为完全数,否则不是完全数。,Program p1(input,output); Var a,b,s:integer; begin for a:=2 to 1000 do begin s:=0; for b:=1 to a-1 do if a mod b=0 then s:=s+b; if

19、a=s then begin write(a,=1); for b:=2 to a-1 do if a mod b=0 then write(+,b); writeln; end; end; end.,例2:水仙花数,求100-999中的水仙花数。(若三位数abc=a3+b3+c3,则abc为水仙花数。因为153=13+53+33=1+125+27,所以153是水仙花数。,例3:搬砖问题,36块砖36人搬,男搬4女搬3,2个小儿抬1砖,要求一次全搬完,问需男、女、小儿各若干?,算法一,算法分析: 1、解的结构和可能解的规模?本题一个解显然包括3个分量:男、女、小儿的人数,可以把解记作(M,W,

20、C),表示男人有M,女人有W,小儿有C,它们的取值范围是:M(0.36) 、W(0.36)、 C(0.36),且C必须是偶数。 2、可能解的生成通过三重循环可以依次生成每一个可能解,而且不重复无遗漏,解空间大小是:37*37*19=26011个可能解。 3、合理解需要满足的条件: 36人:M+W+C=36 36块砖:4*M+3*W+C/2=36,Program example(input,output); var m,w,c:integer; begin for m:=0 to 36 do for w:=0 to 36 do begin c:=0; while c=36 do begin if

21、 (m+w+c=36) and (m*4+w*3+c div 2=36) then writeln(m=,m,w=,w,c=,c); c:=c+2; end; end; End.,算法二,算法优化策略之一:剪枝 考虑到条件:M*4+W*3+C/2=36,容易得出: M*436,即M9. W*336,即W12 综合上述分析,得出更强的结论: M(0.9),W(0.12),C(0,2,4,6,.,34,36) 优化后解的空间大小是:10*13*192470个可能解。不到基本算法的10%。这就是一种很强的优化策略。,这种通过精简循环变量的取值范围从而减少搜索量的策略,通常称为剪枝。,Program

22、example2(input,output); var m,w,c:integer; begin for m:=0 to 9 do for w:=0 to 12 do begin c:=0; while c=36 do begin if (m+w+c=36) and (m*4+w*3+c div 2=36) then writeln(m=,m,w=,w,c=,c); c:=c+2; end; end; End.,算法三,算法优化策略之二:降维 本问题有3个未知量,但只有2个方程: M+W+C=36 M*4+W*3+C/2=36 未知量的个数多于方程的个数,我们把这样的方程(组)通常叫做不定方程

23、(组)。如果我们把未知量的个数减去方程的个数所得的差,称为不定方程的维数,那么本例就是一维不定方程。纯粹的不定方程,有无穷多个解,但是,对于具体问题,往往存在一些隐含限制(如本例中人数必须是非负整数,小儿的人数必须是偶数),使解的个数成为有限个。本例可以抽象为如下数学模型:,求满足如下条件的M,W,C,M+W+C=36 M*4+W*3+C/2=36 M为非负整数 W为非负整数 C为非负整数,两个方程联立,可以消去一个未知量(例如C),得7*M+5*W=36,从这个方程可以得到更强的结论:,M(0.5),W=(36-7*M)/5(前提:36-7*M必须是5的倍数),C=36-M-W,因为本题是一维不定方程,所以只需要一重循环(即用一个未知量作为循环变量),其他未知量可以用赋值语句直接算出,无需使用循环语句,减少了循环层数,这种优化策略常称为降维。,Program example3(input,output); var m,w,c:integer; begin for m:=0 to 5 do if (36-7*m) mod 5=0 then begin w:=(36-7*m) div 5; c:=36-m-w; writeln(m=,m,w=,w,c=,c); end; End.,例 4,给一串整数a1 an,求出它和最大的子序列

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论