算法效率与程序优化

1、算法效率与程序优化在信息学竞赛中，常遇到程序运行超时的情况。然而，同一个程序设计思想，用不同算法，会有不同的运行效率；而即使是同样的算法，由于在代码的细节方面设计有所不同，执行起来效率也会有所不同。当遇到所需时间较长的问题时，一个常数级优化可能是AC的关键所在。下面，我们就从代码细节与算法设计两方面，比较不同程序执行时间的异同，从而选择其中较优的算法，提高程序运行效率。本试验所所采用的的环境是是： CCPU Celleroon 33.066GHzz，内存存2488M，操操作系统统Winndowws XXP SSP2，程序语语言C。编译环环境Deev-cc+。以下称称为1号号机。配配置略好好于N

2、OOIP标标准测试试机CPPU 22.0GGHz。第一章 各种运运算的速速度一、基本本运算的速速度为了增强强算法效效率的计计算准确确性，我我们采用用重复试试验200次取平平均值的的做法。每次试试验运行行100000000000次。基本运行行时间，是指在在准备计计算的运运算复杂杂度之外外，只包包括循环环控制变变量的加加减与比比较所消消耗的时时间。要要从实际际运行时时间中减减去基本本运行时时间，才才是这种种运算真真正的运运行时间间，称为为净运行行时间。#inccluddemainn() innt ii,j; dooublle aa,b,summ=0; foor(jj=0;j220;jj+) /此此

3、处添加加随机数数产生 a=cclocck(); forr(i=0;ii100000000000;ii+);/此处添添加运算算 b=cclocck(); priintff(%lfn,b-aa); summ+=bb-a; prrinttf(anss = %lff,ssum/20.0); geetchh();运行平均均时间是是：2002.33ms。（1）赋赋值运算算净运行时时间0.8mss，与基基本运行行时间2202.3mss相比，可忽略略不计，故以后后将赋值值运算作作为基本本运行时时间的一一部分，不予考考虑。（2）加加法运算算 产生随随机数： x=rrandd();y=raand();循环内加加法

4、：t=x+y;下面的各各种简单单运算只只是更改改运算符符即可，不再写写出代码码。净运行时时间411.455ms，即：在在1s的的时限中中，共可可进行 (10000-2022.3)/ 441.445*11088=1.99*1009次次加法运运算，即即：只通通过循环环、加法法和赋值值的运算算次数不不超过11.9*109.。而应用+=运算算，与普普通加法法时间几几乎相同同，所以+=只是一一种方便便书写的的方法，没有实实质效果果。同样的的，各种种自运算算并不能能提高效效率。（3）减减法运算算 净运行行时间442.995mss，与加加法运算算基本相相同。可见，在计算算机内部部实现中中，把减减法变成成加法

5、的的求补码码过程是是较快的的，而按按位相加加的过程程占据了了较多的的时间，借用化化学中的的一句术术语，可可以称为为整个运运算的“速控步步”。当然，这个“速控步步”的运行行速度受受计算机机本身制制约，我我们无法法优化。在下面面的算法法设计中中，还会会遇到整整个算法法的“速控步步”，针对对这类情情况，我我们要对对占用时时间最多多的步骤骤进行细细心优化化，减少少常数级级运算次次数。（4）乘乘法运算算净运行时时间58.255ms，明显比比加减法法要慢，但不像像某些人人想象的的那样慢慢，至少少速度大大于加减减法的11/2。所以在在实际编编程时，没有必必要把两两个或三三个加法法变成乘乘法，其其实不如如元素

6、乘乘常数来来得快。不必“谈乘色色变”，实际际乘法作作为CPPU的一一种基本本运算，速度还还是很快快的。以上四种种运算速速度都很很快，比比循环所所需时间间少很多多，在普普通的算算法中，每个最内内层循环环约含有有4-55个加、减、乘乘运算，故整个个算法的的运行时时间约为为循环本本身所需需时间的的2倍。（5）除除法运算算净运行时时间12210.2mss，是四四种常规规运算中中最慢的的一种，耗时是是加法的的28倍倍，是乘乘法的221.55倍，确确实如常常人所说说“慢几十十倍”，一秒秒的时限限内只能能运行88.266*1007次次，不足足一亿次次，远大大于循环环时间。所以，在计算算时应尽尽量避免免除法，

7、尤其是是在对时时间要求求较高的的内层循循环，尽尽量不安安排除法法，如果果整个循循环中值值不变，可以使使用在循循环外预预处理并并用一个个变量记记录，循循环内再再调用该该变量的的方法，可以大大大提高高程序运运行效率率。（6）取取模运算算净运行时时间11178.15mms，与与除法运运算速度度几乎相相当，都都非常慢。所以，取模运运算也要要尽量减减少。在在大数运运算而只只要求求求得MOOD NN的值的题题目中，应尽量量利用数数据类型型的最大大允许范范围，在在保证不不超过MMAXIINT的的前提下下，尽量量少执行行MODD运算。例如在循循环数组组、循环环队列的的应用中中，取模模运算必必不可少少，这时时优

8、化运运算便十十分重要要。可利利用计数数足够一一定次数数后再统统一MOOD，循循环完后后再MOOD，使使用中间间变量记记录MOOD结果果等方法法减少次次数。在高精度度计算中中，许多多人喜欢欢边运算边整整理移位位，从而而在内层层循环中中有除、模运算算各一次次，效率率极低。应该利利用innt的数数据范围围，先将将计算结结果保存存至当前前位，在在各位的的运算结结束后再再统一整整理。以下是用用统一整整理法编编写的高高精度乘乘法函数数，规模模为1000000位。int a1100000=0,b100000=00,cc1000000=0;voidd muul() innt ii,j,t; foor(ii=0

9、;i1100000;ii+) ffor(j=00;j100000-i;jj+) cii+j+=aai*bj; foor(ii=0;i999999;i+) cii+1+=cci/100; cii%=10; 以上函数数运行后后，平均均用时2276.55mms。以下是边边运算边边整理的的程序。voidd muul() innt ii,j,t; foor(ii=0;i1100000;ii+) ffor(j=00;jy) x=y;净运行时时间399.1mms，与与加法运运算速度度相当。故比较较运算也也属于较较快的基基本运算算。二、位运运算的速速度（1）左左移、右右移x11;净运行时时间无法法测出，证明位

10、位运算速速度极快快。而使用用自乘计计算需要要64.1mss，自除除运算需需要1664.885mss，所以以尽可能能使用位位运算代代替乘除除。（2）逻逻辑运算算t=x|y; t=xxy; t=x&yy;净运行时时间约30mss，比加加法运算算（约440mss）快较多，是是因为全全是按二二进制位位计算。但加减减与位运运算关系系并不大大，所以以利用位位运算主主要是利利用左右右移位的的高速度度。三、数组组运算的的速度（1）直直接应用用数组for(i=00;i100000;i+) ffor(k=00;k100000;k+) t=qkk;净运行时时间399.855ms。这里计计算了内内层循环环的时间间。若

11、改改为for(i=00;i100000000000;i+) t=q00;则净运行行时间为为1.550mss，很快快，与2202.3mss的循环环时间相相比，可可以忽略略。故应应用数组组，速度度很快，不必担担心数组组寻址耗耗时。同同时我们们发现，循环耗耗时在各各种运算算中是很很大的，仅次于于乘除，故我们们要尽量量减少循循环次数数，能在在一个循循环中解解决的问问题不放放在两个个循环中中，减少少循环变变量次数数。（2）二二维数组组for(i=00;i50000;ii+) foor(kk=0;k550000;k+) t=zzik;实际运行行时间为为80.45mms，若若规模扩扩至1000000则100

12、s内无无法出解解，由于于频繁访访问虚拟拟内存。可以试试想，若若物理内内存足够够大，则则运行时时间约为为3200ms，仅为为2022.3mms的基基准运行行时间的的3/22，差距距似乎并不不是很大大；由此此推得其其净运行行时间约约为1220mss。但相相较加、减等简简单操作作，速度度仍为33倍，尤尤其与几几乎不需需时间的的一维数数组相比比差距巨巨大。尤尤其是在在计算中中，二维维数组元元素经常常调用，时间效效率不可可忽视。所以，对于已已知数目目不多的的同样大大小的数数组，可可用几个个变量名名不同的的一维数数组表示示，如xx、y方方向，两两种不同同参数，而不要要滥用二二维数组组。在滚滚动数组组中，可

13、可用两个个数组交交替计算算的方式式，用二二维数组组同样较较慢。四、实数数运算的的速度测试方法法与“基本运运算”类似。（次数数：100000000000，单单位：mms）运算符=+-*/%longg intt43.00531.33-74.7569.555299.65360.5int66441.44514.9957.9566.412433.45518588.855doubble46.11510.22512.6633.66517533.555-由上表可可见，涉涉及乘除除、取模模时innt644很慢，要慎用用；innt显然然最快，但对大大数据要要小心越越界。若若一组变变量中既既有超出出intt的，又又

14、有不超超过innt的，则要分分类处理理，不要要直接都都定义成成intt64，尤其在在乘除模模较多的的高精度度过程中中。以上讨论论了主要要基本运运算的速速度问题题。概括括起来说说，除、模最慢慢，二维维数组较较慢，加加减乘、逻辑位位运算、比较大大小较快快，左右右移位、一维数数组、赋赋值几乎乎不需要要时间。而循环环forr或whhilee语句十分分特殊，它的运运算速度度大于判判断大小小、自加加控制变变量所用用时间之之和，无无论采用用内部iif判断断退出，还是在在入口处处判断，都回用用去约2200mms的时时间。所所以尽量量减少循循环次数数，是优优化算法法的关键键。对于于双层或或多层的的循环，应把循循

15、环次数数少的放放在最外外层，最最大的循循环位居居最内部部，以减减少内层层循环的的执行次次数。第二章 各种算算法的速速度一、排序序算法的的速度1.冒泡泡排序for(i=00;i200000;i+) aai=raand();s=cllockk();for(i=00;in;ii+) foor(jj=0;jaaj) tt=ai; aai=aj; aaj=t; b=cclocck();运行时间间：14407mms2.选择择排序for(i=00;i200000;i+) ai=rannd(); s=cloock(); foor(ii=0;inn;i+) maxx=0; forr(j=0;jjammax) m

16、max=j; bii=aamaax; ammax=-1100000000; t=cloock();运行时间间：12220mms3.插入入排序for(i=00;i200000;i+) ai=rannd(); s=cclocck(); foor(ii=0;i=0;j-) iff(ajt) bbreaak; forr(l=i;llj+1;ll-) al=all-1; ajj+1=t; t=cclocck();运行时间间：9844ms以上三种种都是OO(n2)的的排序，其中插插入排序序最快，且可以以用指针针加以优优化。从从编程复复杂度上上，冒泡泡排序最最简单。从算法法的稳定定性上，插入排排序是稳稳定的

17、，即排序序后关键键字相同同的记录录顺序不不改变，特别适适用于表表达式处处理等问问题。一般的的选择排排序是不不稳定的的，但这这里给出出的程序序由于使使用了人人类最原原始的方方法，即即依次选选择最大大的并排除，故是稳稳定的。冒泡排排序是不不稳定的的，涉及及必须保保持数据据原顺序序的题目目时不能能选择冒冒泡排序序，而必必须选择择稳定的的排序方方式。以下试验验所采用用的环境境是： CPUU Inntell Coore 1.773GHHz*22，内存存5122M，操作作系统WWinddowss 7 Ulttimaate Betta，程程序语言言C。编编译环境境Devv-c+，以以下称为为2号机机。由于C

18、CPU速速度较慢慢，且操操作系统统占用资资源较多多，程序序运行速速度明显显减慢，第一章章的“基本运运行测试试”需要时时间约为为前者的的2倍，即为4406mms。故故第一章章的程序序运行时时间此处处应乘22。4.快速速排序的的标准版#deffinee MAAX 11000000000int aMMAX;int p(iint l,iint r) innt xx=al,i=ll-1,j=rr+1,t; whhilee(1) do-jj; whhilee(ajx); if(ijj) tt=ai;aii=aaj;aj=t; elsse rretuurn j; voidd q(intt l,intt r)

19、 innt nn; iff(lr) n=pp(l,r); q(ll,n); q(nn+1,r); 运行时间间：29948mss。注意意：不要要以为三三种平方方级排序序方法的的速度与与快速排排序可比比拟，因因为平方方级的数数据范围围是1000000，而快快速排序序的范围围是10000000000。对于1100000的数数据，快快速排序序只需33.1mms。另另外，快快速排序序不是稳稳定的排排序，需需要保持持原顺序序的不能能用此法法。voidd p(intt l,intt r) innt xx=al,i=ll-1,j=rr+1,t; iff(lr) whhilee(1) do-jj; whhile

20、e(ajx); if(ijj) tt=ai;aii=aaj;aj=t; elsse bbreaak; p(l,jj); p(j+11,r); 若程序改改为以上上形式，则运行行时间为为29117mss，稍快快了一些些，是因因为减少少了函数数调用次次数。对对于函数数调用，我们进进行这样样的测试试。s=cllockk();for(i=00;i100000000000;i+) ttestt();t=cllockk();int tesst() innt nn; n+;净运行时时间2000mssint tesst() innt nn;净运行时时间844msint tesst()净运行时时间10ms由此可见

21、见，调用用函数本本身并不不浪费时时间，仅仅相当于于循环本本身时间间4000ms的的1/440，相相当于加加法800ms的的1/88，是很很快的运运算。但由于于在函数内内部需要要进行现现场保护护，调用用系统堆堆栈，所所以用时时大幅增增加，定定义变量量后只是是一个自自增运算算就用去去1200ms，相当于于主程序序中加法法运算时时间的33/2倍。故函数中中的运算算比主程程序中要要慢，尤尤其是反反复调用用函数，会增加加不必要要的时间间开销。所以，一些简简单的功功能尽量量在一个个函数或或主程序序内完成成，不要要使用过过多的函函数；涉涉及全局局的变量量不要在在函数调调用时由由接口给给出，再再返回值值，尽量

22、量使用全全局变量量。这些些方法可可能使程程序的可可读性降降低，不不利于调调试，但但有利于于提高时时效，正正如汇编编语言程程序比高高级语言言快一样样。5.优化化的快速速排序（1）用用插入排排序优化化由于递归归调用浪浪费大量量时间，本算法法的思想想是，当当首尾间间距小于于minn时，改改用效率率较高的的插入排排序，减减少反复复递归。这个想想法是好好的，但但运行效效果并不不如人意意。当mmin=4时，程序运运行时间间降为229011ms，优化幅幅度不大大，且增增加了编编程复杂杂度，故故不宜采采用。其其原因是是递归调调用、插插入排序序内部循循环所用用时间过过长。（2）用用小数据据判断优优化 iff(l

23、+1rr) whhilee(1)/与普通通快速排排序相同同 ellse if(l+11=rr&aalar) tt=ai;aii=aaj;aj=t;仅就区间间长度为为2的情情况进行行判断优优化，减减少一次次递归调调用，就就能使运运行时间间缩短为为26999mss，降低低了2000mss以上。而区间间长度不不小于33的直接接判断有有困难。快速排序序运行时时间（单单位：mms）数据规模模10000010000001000000001000000000原始快速速排序1.50025.220258.5527166.455优化快速速排序2.30023.440245.4025644.8006.归并并排序归并排

24、序序是一种种稳定的的排序方方法，且且时间效效率与快快速排序序相同，都是OO(nllognn)。但但归并排排序比快快速排序序的常数数因子大大，故快快速排序序还是最最快的排排序方法法。归并并排序则则适用于于有特殊殊要求的的题目，如不满满足交换换律的表表达式处处理。int aMMAX,bMAXX;voidd coombiine(intt frrom,intt too) innt ii,t,midd=(ffromm+too)/22,f,r; iff(frrom=too|ffromm+1=too) rretuurn; iff(frrom+2=to) if(affrommarr) bii+=af+; ee

25、lsee bi+=aar+; foor(ii=frrom;itto;ii+) aai=bi; 调用：ccombbinee(0,MAXX);归并排序序算法还还可用于于统计逆逆序对数数。所谓谓逆序对对，即为为在一个个数组aa中，满满足iaj（或aiajj，依依排序方方向而定定）的点(ii,j)的个数数。voidd soort(intt frrom,intt too) innt ii,t,midd=(ffromm+too)/22,f,r; iff(frrom=too|ffromm+1=too) rretuurn; iff(frrom+2=to) if(affrommarr) bii+=af+; ee

26、lsee bi+=aar+; iff(f!=miid) ttot+=(mmid-froom); foor(ii=frrom;itto;ii+) aai=bi; 主函数： soort(0,nn); prrinttf(%d,n*(n-1)/2-ttot);7.多关关键字排排序多关键字字排序，经常出出现于要要求按某某要素排排序姓名名，该要要素相同同的按字字典序排排列的题题目。这这样，此此要素是是第一关关键字，姓名是是第二关关键字。qistt(0,n-11);j=0;for(i=11;i0); do+ii; whhilee(sttrcmmp(nnameelooj,nnameelooi)0); if(i

27、jj) tt=looi;looi=looj;looj=t; elsse bbreaak; iff(lr) qnnamee(l,j); qnnamee(j+1,rr);上述排序序方法，实质上上是将普普通快速速排序中中的数大大小比较较换成字字符串大大小比较较。为了了避免字字符串交交换浪费费时间，采用了了类似指指针的定定位数组组，只需需交换定定位数组组的元素素即可。当然，用指针针直接实实现效率率更高。关于字符符串比较较函数sstrccmp的的时间效效率，我我们有如如下试验验：for(i=00;i1000;i+) ai=rannd(); bii=rrandd();s=cllockk();for(i=0

28、0;ibbi) reeturrn 11; if(aiibbi) reeturrn -1; reeturrn 00; 运行时间间：11131mms，净净运行时时间约7725mms，相当于于9次整整数比较较时间，比标准准库函数数稍慢。显然，标准库函函数是经经过精心心优化的的，我们们在有库库函数可可用时尽尽量用库库函数，不仅降降低编程程复杂度度，降低低错误率率，还能能提高时时间效率率。9.Haash排排序#deffinee MOOD 99999997/Ass a bigg prrimee#deffinee MAAX 1100000/As thee maax llenggth of thee sttr

29、inngint ELFFhassh(ccharr *kkey) unnsiggnedd loong h=00; whhilee(*kkey) h=(h24; h&=g; reeturrn hh%MOOD;Hashh排序，就是先先对读入入的字符符串求HHashh值。第第一种方方案是，再对HHashh值进行行快速排排序，最最后应用用二分搜搜索查找找。此时时无需MMOD大大质数。第二种种方案是是，将HHashh值MOOD后，放入HHashh表中，并用开开散列等等方法处处理冲突突。显然然，第二二种方案案更优，但编程程复杂度度也较高高。综上所述述，在选选择适当当的排序序算法时时，要注注意时间间复杂度度和

30、编程复复杂度，同时保保证满足足题意。二、最短短路算法法的比较较在图论中中，最短短路算法法是常见见的。对对于常见见的几种种算法，到底哪哪种更优优，还是是各有千千秋？我我们不妨妨一试。以下实实验在11号机上上进行，均为试试验200次随机机数取平平均值的的结果。1.单源源最短路路径dijjksttra算算法voidd diijksstraa() innt ii,j,minn=0; foor(ii=0;inn;i+) ddisi=d00ii; foor(ii=1;inn;i+) minn=n; forr(j=0;jjn;j+) iff(!uusej&dijdiimmin) mmin=j; useemi

31、in=1; forr(j=0;jjn;j+) iff(diismmin+dminnjjddisj) ddisj=dissmiin+dmminj; 随机数产产生器：for(i=00;iMAXX;i+) foor(jj=0;jMMAX;j+) iif(ii!=jj) diijj=rrandd();当MAXX=20000时时（即点点数为220000个），运行时时间：228.22ms。当当MAXX更大时时，内存存会使用用过多，故在11s时限限内至多多运行规规模为220000的单源源最短路路径355次。2.单源源最短路路径Forrd算法法int forrd() innt ii,j; foor(ii=1;

32、inn;i+) ddi=MAAXINNT; foor(ii=1;inn;i+) ffor(j=00;jnumm;j+) iff(dfjj+wjjddej) ddej=dfjj+wjj; foor(jj=0;jnnum;j+) iif(ddfj+wjdeej) retturnn 0; reeturrn 11; 数据构构造：110*nn条随机机边。当当n=110000时，运运行时间间：499.955ms。当n=100000时时，运行行时间：67666mss。数据构构造：nn*n条条边的完完全图。当n=10000时，运行时时间64469mms。比比Dijjksttra和和SPFFA都慢慢很多，因为其

33、其算法的的理论时时间复杂杂度就达达到了OO(VEE)，属属于介于于O(nn2)与O(n33)的算算法。但我们们仍然需需要这种种算法，因为当当图中存存在负权权时，必必须使用用Forrd算法法。同时时，该算算法还能能判断图图中是否否存在负负权回路路（无解解）。3.单源源最短路路径SPFFA算法法struuct missingg intt nuum; intt pooo; strructt miisinng *p; ;int worr50000000;int diss6000011;int yess6000011=0;int begg=0,endd=1;mainn() iint n,mm; iint

34、 a,bb,c,i; sstruuct missingg q600001,*qqq6600001,*x; ddoubble s,tt; FFILEE *ffp; ffp=ffopeen(1.ttxt,rr); ffscaanf(fp,%dd%d,&nn,&mm); ffor(i=00;in;ii+) qqqii=&qii; ffor(i=00;ip=(strructt miisinng *)maallooc(ssizeeof(strructt miisinng); qqqbb-p=(strructt miisinng *)maallooc(ssizeeof(strructt miisinng)

35、; qqqaa=qqqaa-p; qqqbb=qqqbb-p; qqqaa-pooo=b; qqqbb-pooo=a; qqqaa-numm=qqqb-nnum=c; ss=cllockk(); ffor(i=00;ip=NNULLL; ddisi=-1; yyes0=1; wwor0=0; ddis0=0; wwhille(bbeg!=ennd) xx=qworrbeeg.p; wwhille(xx!=NNULLL) if(ddisx-pooo=-1|(ddisx-poooxx-nnum+disswoorbbeg&dissx-pooo!=-11) ddisx-pooo=ddisworrbee

36、g+x-nuum; wworendd=xx-ppoo; iif(yyesx-pooo=0) yyesx-pooo=11; eend+; xx=x-p; yyesworrbeeg=0; bbeg+; pprinntf(%dd,ddisn-11); tt=cllockk();随机数生生成模块块： fprrinttf(ffp,%d %dn,n,110*nn); forr(i=0;ii100*n;i+) j=rrandd()%n+11; kk=raand()%nn+1; wwhille(jj=kk) j=rrandd()%n+11; kk=raand()%nn+1; ffpriintff(fpp,%d

37、 %d %dnn,jj,k,rannd(); 运行时间间（不含含文件操操作）：当n=10000000时，运运行时间间19337mss；当nn=1000000时，运运行时间间1411ms；当n=10000时，运行时时间小于于10mms。特别需需要注意意的是，当n=500000时时，用时时8288ms，再加上上文件操操作用时时，可称称为是SPFFA算法法数据规规模的上上限。这这组数据据是n个个点，110*nn条随机机边的情情况下作作出的。若使用用O(nn2)的Diijksstraa算法，时间将将大幅增增加。对于单源源最短路路径，要要考虑题题意要求求，稀疏疏图使用用SPFFA，密密集图使使用Diij

38、ksstraa，以提提高运行行效率。3.点对对点最短短路径Flloyeed算法法voidd flloyeed() innt ii,j,k,mmin=0; foor(kk=0;knn;k+) ffor(i=00;in;ii+) forr(j=0;jjn;j+) iff(dik+dkkjjddij) ddij=dik+dkkjj;当MAXX=5000时，运行时时间：9979.85mms。这这提示我我们，点点对点最最短路径径的规模模最大为为5000，否则则会超时时。若使用MMAX-1次ddijkkstrra算法法voidd diijksstraa() innt ii,j,k,mmin=0; foor

39、(kk=0;knn-1;k+) intt usseMMAX=00; foor(ii=0;inn;i+) ddisi=dkkii; foor(ii=1;inn;i+) minn=n; forr(j=0;jjn;j+) iff(!uusej&dijdiimmin) mmin=j; useemiin=1; forr(j=0;jjn;j+) iff(diismmin+dminnjjddisj) ddisj=dissmiin+dmminj; 当MAXX=5000时，运行时时间：116255ms，与flloyeed的9980mms相比比，显然然慢了很很多。因因此，ffloyyed算算法是点点对点最最短路径

40、径的“正统”算法。三、字符符串匹配配算法的的比较1.朴素素匹配算算法for(i=00;i10000;ii+) Si=1; forr(j=0;jj10000000;jj+) Tj=1; s=cclocck(); tott=0; ls=strrlenn(S); lt=strrlenn(T); forr(i=0;iiltt-lss;i+) ffor(j=00;jls;j+) if(Tii+j!=SSj) brreakk; iif(jj=lls) tott+; priintff(%d ,toot); t=cclocck();运行时间间：3335.335mss。这组组测试数数据是：原串11000000个

41、个1，匹匹配串110000个1.若使用更更极端的的数据，如匹配配串1000000个1，则需要要数秒出出解，显显然过慢慢。对于于随机数数据，由由于匹配配的可能能性极小小，用时时很快是是必然的的。我们们只考虑虑极端数数据。2.KMMP算法法（优化化）int KMPP() innt ii,q=0; foor(ii=1;i0&Tq+11!=Sii) q=nnexttq; iif(TTq+1=Si) q+; iif(qq=llt) attot+=i-llt+11; voidd fff() intt q,k; forr(q=1;qq0&Tkk+1=TTq+1) kk=neextk; neextq=k; v

42、oidd f() intt q,k; nexxt11=00;k=0; forr(q=2;qq0&Tk+11!=Tqq) k=nnexttk; iif(TTk+1=Tq) k=kk+1; nnexttq=k; 调用过程程： f(); fff(); KMMP();算法说明明：函数数f计算算初始“回复位位置”，函数数ff计计算优化化后的“回复位位置”，函数数KMPP是依赖赖上述“回复位位置”进行快快速匹配配的算法法。Si为为待匹配配串，TTi为目标标串，nnextti计算“回复位位置”。运行时间间：当目标串串长10000，匹配串串长10000000时00.8mms。目目标串长长1000时2.3mss

43、。目标标串长110或1100000时，运行时时间1.55ms。可可见，KKMP算算法极快快，确实实是O(n)的的时间复复杂度。故正确确的优化化KMPP算法是是不会超超时的。同样，优化KKMP与与普通KKMP的的差距也也很明显显，尤其其是在极极端数据据时。四、最小小生成树树算法的的比较1.Prrim算算法voidd prrim() innt llowccostt20002,clloseet220022,ii,j,k,mmin,tott=0; foor(ii=1;i=n;ii+) lowwcosstii=ccostt1i; cloosetti=1; foor(ii=1;inn;i+) minn=M

44、AAXINNT; forr(j=1;jj=nn;j+) iff(loowcoostjminn&llowccosttj!=00) minn=loowcoostj; k=jj; tott+=llowccosttk; lowwcosstkk=00; forr(j=1;jj=nn;j+) iff(coostkjlowwcosstjj) lowwcosstjj=ccosttkj; cloosettj=k; prrinttf(%d ,ttot);随机数生生成：for(i=11;i=MAAX;ii+) foor(jj=1;j=MAXX;j+) iif(ii!=jj) cosstiijj=rrandd();当

45、数据范范围MAAX=220000时，平均均运行时时间：446.995mss。 由于Prrim算算法是OO(n2)的的，速度度快不是是偶然。由此可可见，最最小生成成树不是是程序运运行时间间的瓶颈颈。从算算法上看看，我们们注意到到Priim算法法十分类类似求单单源最短短路径的的Dijjksttra算算法。两两种算法法都是先先找出不不在集合合中的最最近元素素，将其其加入集集合，并并对该元元素连接接的点进进行松弛弛操作，更新各各点到集集合的距距离。在在具体实实现中，都是利用用一个数数组记录录每个点点到集合合的距离离，点在在集合中中用距离离为零表表示。2.Krruskkal算算法（较差）int fatt

46、herr(innt xx) iff(seetxx!=x) ssetx=fattherr(seetxx); reeturrn ssetx;voidd krruskkal() innt ii,j,staart,endd,vaaluee,coost=0; foor(ii=0;inn;i+) sseti=i; foor(kk=1;knn;k+) vaaluee=MAAXINNT; foor(ii=0;inn;i+) ffor(j=00;jn;jj+) if(i!=j&fattherr(i)!=ffathher(j) iff(daataijvallue) staart=i; endd=j; vallue

47、=dattaiijj; ccostt+=vvaluue; ssetfattherr(sttartt)=fattherr(ennd); pprinntf(%dd ,cosst);当规模MMAX=5000时，运运行时间间：35563mms。显显然，当当图为密集集矩阵时时，Krruskkal算算法并不不迅速。但当图为为稀疏图图时，算算法的优优势便很很明显了了。3.Krruskkal算算法（优优化）int finnd(iint x) iff(fx!=x) ffx=fiind(fxx); reeturrn ffx;voidd krruskkal() innt ii,j,a,bb,toot=00,nuum

48、=00; foor(ii=0;inn;i+) ffi=i; foor(ii=0;inn;i+) a=ffindd(si); b=ffindd(ei); if(a!=b) nnum+; ttot+=wi; ffa=b; iif(nnum=maax) breeak; prrinttf(%d ,ttot);主程序：for(i=11;in;ii+) ffi=raand()%mmax; eei=raand()%mmax; wwi=raand(); s=cclocck(); sorrt(00,n-1); kruuskaal(); t=cclocck();此处soort函函数是快快速排序序函数，采用了了本文

49、上上述“优化的的快速排排序算法法”。当maxx=10000000时，即共11000000个个点，共共100000000条边边时，平均均运行时时间为4409.4mss。当maax=1100000时，平均运行行时间为为43.7mss。完全全满足时时限1ss的要求求。而若若使用OO(n2)的的Priim算法法，运行行时间将将不可思思议。故故Kruuskaal算法法十分适适合稀疏疏图的处处理。我们再来来看Krruskkal算算法对于于密集图图的效率率。for(i=00;imaxx;i+) foor(jj=0;jmmax;j+) fii=ii; eii=jj; wii=rrandd(); 当maxx=2

50、0000时，平平均运行行时间113944.5mms，比比Priim的447mss慢了约330倍。通过单单独测试试sorrt时间间可知，当数目目过多时时，快速速排序占占去很多多的时间间（平均均12999.33ms），而Krruskkal算算法本身身仍然很很快（不不到1000mss）。综上所述述，在解解题前，务必看看清题中中给出的的图是密密集图还还是稀疏疏图，并并选择合合适的算算法，否否则程序序运行速度度会很慢慢。五、拓扑扑排序算算法int tuoopu() innt ii,j,k; foor(ii=0;inn;i+) ffor(j=00;jn;jj+) if(aiijj) dj+; foor(i

51、i=0;inn;i+) forr(j=0;jjn;j+) iff(dj=0) bbreaak; if(j=n) reeturrn 00; djj=-1; anssi=j; forr(k=0;kkn;k+) iff(ajk) ajjkk=00; dkk-; reeturrn 11;取随机数数据测试试：当nn=10000时时，运行行时间：15mms；当n=220000时，运运行时间间：633ms。当n过过大时，数组将将越界。六、搜索索算法的的比较1.朴素素深度优优先搜索索程序框架架：（函函数依具具体题目目而定）voidd opp(innt nnow)voidd reead()voidd prrin

52、tt()voidd prrintterrror()int anss(innt nnow)int s(iint noww) innt ii,fllag; iff(noow=n) if(anss(noow) reeturrn 11; retturnn 0; foor(ii=0;inn;i+) op(i); flaag=ss(noow+11); if(flaag) reeturrn 11; reeturrn 00;mainn() innt fflagg; reead(); fllag=s(00); iff(fllag) pprinnt(); ellse priinteerroor(); reetur

53、rn;以经典的的“八皇后后问题”为例。voidd quueenn(innt xx,innt yy) innt ii,a,b; iff(x=n-1) tott+; retturnn; foor(ii=x;inn;i+) uuseiy=1; a=x+11;b=y+11; whhilee(an&bnn) uusea+bb+=1; a=x+11;b=y-11; whhilee(a=0) uusea+bb-=1; foor(ii=0;inn;i+) iif(!useex+1i) queeen(x+11,i); foor(ii=x;inn;i+) uuseiy=0; a=x+11;b=y+11; whhi

54、lee(an&bnn) uusea+bb+=0; a=x+11;b=y-11; whhilee(a=0) uusea+bb-=0; 当n=8时，速度无无法测出出。当n=99时，用用时1009mss。当nn=100时，用用时24406mms。可可见，朴朴素的回回溯算法法在八皇皇后问题题中，所所用时间间随N的的增大而而迅速增增大，复复杂度几几乎为NN！。2.位运运算voidd teest(lonng rrow,lonng lld,llongg rdd) llongg p,poss; iif(rrow!=uppperrlimm) poos=uuppeerliim&(roow|lld|rrd); wh

55、hilee(poos) p=poss&(-poss); poos-=p; teest(roww+p,(ldd+p)1); ellse suum+;主程序： summ=0; uppperllim=(1n)-1; tesst(00,0,0);运行时间间：当nn=111时，时时间无法法测出。当n=12时，用时时15mms；当当n=113时，用时1125mms；当当n=114时，用时6672mms；当当n=115时，用时339844ms。虽然增增长速度度也较快快，不属属于多项项式算法法，但比比起朴素素算法要要快很多多。原因因主要是是，把棋棋盘的nn*n个个格变成一一个数，免去对数数组的操操作；采采用位

56、运运算，比比算术运运算要快快。最重重要的是是，判重重时直接用用数的比比较，速速度很快快。由此可见见，对搜搜索问题题，优化化的空间间还是很很大的。3.广度度优先搜搜索广度优先先搜索的的时间复复杂度从从理论上上说，搜搜索完整整棵树与与深度优优先搜索索的相同同，只是是适用范范围不同同。两者者的根本本区别在在于，实实现方式式一个是是栈，先先进先出出；一个个是队列列，先进进后出。主要的的瓶颈是是空间问问题，数数组不能能太大，必要时时使用循循环队列列解决。程序框架架：（函函数依具具体问题题而定）voidd reead()voidd prrintt()/priint lasst aa as thee ann

57、sweerint op()/rretuurn ressultt maade deppenddingg onn laast aint anss()/tesst llastt a iif iit iis tthe ansswerrvoidd s(intt frrom) innt ii,t=numm; foor(ii=frrom;itt;i+) if(anss() reeturrn; annum+=op(); s(t); mainn() reead(); s(0); prrintt();以图论中中的“种子填填充法”为例：（计算算某点开开始的连连通图形形面积）#inccluddeint n,mm,a1

58、000010000=0,x1000010000=0;int filll(iint i,iint j) innt ttot=1; iff(aij=0|xij=1) rretuurn 0; xij=1; toot+=filll(ii-1,j); toot+=filll(ii+1,j); toot+=filll(ii,j-1); toot+=filll(ii,j+1); reeturrn ttot; mainn() innt ii,j,tott=0; sccanff(%d%dd,&n,&m); foor(ii=1;i=n;ii+) ffor(j=11;j=m;j+) scaanf(%dd,&aiij

59、j); foor(ii=1;i=n;ii+) ffor(j=11;j=n;j+) if(xiijj=0&aiijj=1) prrinttf(Bloock %d: att (%d,%d) Sizze %dnn,+toot,ii,j,filll(ii,j); geetchh();当n=110000时，随随机数实实验表明明，平均均运行时时间为114.11ms。（当心心系统堆堆栈溢出出！）事事实上，由于前前面填充充时已经经填入大大部分点点，则采采用记忆忆化搜索索的办法法，同在在一个区区域中的的点不必必重新搜搜索，故故算法效效率仍为为O(nn2)。4.线性性搜索（二分法法）int seaarchh(in

60、nt ffromm,innt tto,iint x) iff(a(frrom+to)/2=xx) rretuurn (frrom+to)/2; iff(frrom=too|ffromm+1=too) rretuurn -1; iff(a(frrom+to)/2x) rretuurn seaarchh(ffromm+too)/22,too,x); reeturrn ssearrch(froom,(froom+tto)/2,xx); 主函数：（重复复100000000次，便于测测量时间间，此时时循环时时间可忽忽略）for(i=00;i1; iff(at=x) rretuurn t; iff(frr