鄂教版信息技术九下第9课《程序调试优化算法》教案

1、算法效率与程序优化石家庄二中 李博杰在信息学竞赛中，常遇到程序运行超时的情况。然而，同一个程序设计思想，用不同算法，会有不同的运行效率；而即使是同样的算法，由于在代码的细节方面设计有所不同，执行起来效率也会有所不同。当遇到所需时间较长的问题时，一个常数级优化可能是AC的关键所在。下面，我们就从代码细节与算法设计两方面，比较不同程序执行时间的异同，从而选择其中较优的算法，提高程序运行效率。本试验所采用的环境是： CPU Celeron 3.06GHz，内存248M，操作系统Windows XP SP2，程序语言C。编译环境Dev-c+。以下称为1号机。配置略好于NOIP标准测试机CPU 2.0G

2、Hz。第一章 各种运算的速度一、基本运算的速度为了增强算法效率的计算准确性，我们采用重复试验20次取平均值的做法。每次试验运行100000000次。基本运行时间，是指在准备计算的运算复杂度之外，只包括循环控制变量的加减与比较所消耗的时间。要从实际运行时间中减去基本运行时间，才是这种运算真正的运行时间，称为净运行时间。#include<stdio.h>main() int i,j; double a,b,sum=0; for(j=0;j<20;j+) /此处添加随机数产生 a=clock(); for(i=0;i<100000000;i+);/此处添加运算 b=clock

3、(); printf("%lfn",b-a); sum+=b-a; printf("ans = %lf",sum/20.0); getch();运行平均时间是：202.3ms。（1）赋值运算净运行时间0.8ms，与基本运行时间202.3ms相比，可忽略不计，故以后将赋值运算作为基本运行时间的一部分，不予考虑。（2）加法运算 产生随机数： x=rand();y=rand();循环内加法：t=x+y;下面的各种简单运算只是更改运算符即可，不再写出代码。净运行时间41.45ms，即：在1s的时限中，共可进行 (1000-202.3)/ 41.45*108=1.

4、9*109次加法运算，即：只通过循环、加法和赋值的运算次数不超过1.9*109.。而应用+=运算，与普通加法时间几乎相同，所以+=只是一种方便书写的方法，没有实质效果。同样的，各种自运算并不能提高效率。（3）减法运算 净运行时间42.95ms，与加法运算基本相同。可见，在计算机内部实现中，把减法变成加法的求补码过程是较快的，而按位相加的过程占据了较多的时间，借用化学中的一句术语，可以称为整个运算的“速控步”。当然，这个“速控步”的运行速度受计算机本身制约，我们无法优化。在下面的算法设计中，还会遇到整个算法的“速控步”，针对这类情况，我们要对占用时间最多的步骤进行细心优化，减少常数级运算次数。（

5、4）乘法运算净运行时间58.25ms，明显比加减法要慢，但不像某些人想象的那样慢，至少速度大于加减法的1/2。所以在实际编程时，没有必要把两个或三个加法变成乘法，其实不如元素乘常数来得快。不必“谈乘色变”，实际乘法作为CPU的一种基本运算，速度还是很快的。以上四种运算速度都很快，比循环所需时间少很多，在普通的算法中，每个最内层循环约含有4-5个加、减、乘运算，故整个算法的运行时间约为循环本身所需时间的2倍。（5）除法运算净运行时间1210.2ms，是四种常规运算中最慢的一种，耗时是加法的28倍，是乘法的21.5倍，确实如常人所说“慢几十倍”，一秒的时限内只能运行8.26*107次，不足一亿次，

6、远大于循环时间。所以，在计算时应尽量避免除法，尤其是在对时间要求较高的内层循环，尽量不安排除法，如果整个循环中值不变，可以使用在循环外预处理并用一个变量记录，循环内再调用该变量的方法，可以大大提高程序运行效率。（6）取模运算净运行时间1178.15ms，与除法运算速度几乎相当，都非常慢。所以，取模运算也要尽量减少。在大数运算而只要求求得MOD N的值的题目中，应尽量利用数据类型的最大允许范围，在保证不超过MAXINT的前提下，尽量少执行MOD运算。例如在循环数组、循环队列的应用中，取模运算必不可少，这时优化运算便十分重要。可利用计数足够一定次数后再统一MOD，循环完后再MOD，使用中间变量记录

7、MOD结果等方法减少次数。在高精度计算中，许多人喜欢边运算边整理移位，从而在内层循环中有除、模运算各一次，效率极低。应该利用int的数据范围，先将计算结果保存至当前位，在各位的运算结束后再统一整理。以下是用统一整理法编写的高精度乘法函数，规模为10000位。int a10000=0,b10000=0,c10000=0;void mul() int i,j,t; for(i=0;i<10000;i+) for(j=0;j<10000-i;j+) ci+j+=ai*bj; for(i=0;i<9999;i+) ci+1+=ci/10; ci%=10; 以上函数运行后，平均用时27

8、6.55ms。以下是边运算边整理的程序。void mul() int i,j,t; for(i=0;i<10000;i+) for(j=0;j<10000-i;j+) ci+j+1+=(ci+j+ai*bj)/10; ci+j=(ci+j+ai*bj)%10; 以上函数运行后，平均用时882.80ms。统一整理与边整理边移位相比，快了3.2倍，有明显优势。故尽量减少除法、取模运算的次数，是从常数级别降低时间复杂度的方法。（7）大小比较if(x>y) x=y;净运行时间39.1ms，与加法运算速度相当。故比较运算也属于较快的基本运算。二、位运算的速度（1）左移、右移x<&

9、lt;1; x>>1;净运行时间无法测出，证明位运算速度极快。而使用自乘计算需要64.1ms，自除运算需要164.85ms，所以尽可能使用位运算代替乘除。（2）逻辑运算t=x|y; t=xy; t=x&y;净运行时间约30ms，比加法运算（约40ms）快较多，是因为全是按二进制位计算。但加减与位运算关系并不大，所以利用位运算主要是利用左右移位的高速度。三、数组运算的速度（1）直接应用数组for(i=0;i<10000;i+) for(k=0;k<10000;k+) t=qk;净运行时间39.85ms。这里计算了内层循环的时间。若改为for(i=0;i<10

10、0000000;i+) t=q0;则净运行时间为1.50ms，很快，与202.3ms的循环时间相比，可以忽略。故应用数组，速度很快，不必担心数组寻址耗时。同时我们发现，循环耗时在各种运算中是很大的，仅次于乘除，故我们要尽量减少循环次数，能在一个循环中解决的问题不放在两个循环中，减少循环变量次数。（2）二维数组for(i=0;i<5000;i+) for(k=0;k<5000;k+) t=zik;实际运行时间为80.45ms，若规模扩至10000则10s内无法出解，由于频繁访问虚拟内存。可以试想，若物理内存足够大，则运行时间约为320ms，仅为202.3ms的基准运行时间的3/2，差

11、距似乎并不是很大；由此推得其净运行时间约为120ms。但相较加、减等简单操作，速度仍为3倍，尤其与几乎不需时间的一维数组相比差距巨大。尤其是在计算中，二维数组元素经常调用，时间效率不可忽视。所以，对于已知数目不多的同样大小的数组，可用几个变量名不同的一维数组表示，如x、y方向，两种不同参数，而不要滥用二维数组。在滚动数组中，可用两个数组交替计算的方式，用二维数组同样较慢。四、实数运算的速度测试方法与“基本运算”类似。（次数：100000000，单位：ms）运算符=+-*/%long int43.0531.3-74.7569.55299.65360.5int6441.4514.957.9566.

12、41243.451858.85double46.1510.2512.633.651753.55-由上表可见，涉及乘除、取模时int64很慢，要慎用；int显然最快，但对大数据要小心越界。若一组变量中既有超出int的，又有不超过int的，则要分类处理，不要直接都定义成int64，尤其在乘除模较多的高精度过程中。以上讨论了主要基本运算的速度问题。概括起来说，除、模最慢，二维数组较慢，加减乘、逻辑位运算、比较大小较快，左右移位、一维数组、赋值几乎不需要时间。而循环for或while语句十分特殊，它的运算速度大于判断大小、自加控制变量所用时间之和，无论采用内部if判断退出，还是在入口处判断，都回用去约

13、200ms的时间。所以尽量减少循环次数，是优化算法的关键。对于双层或多层的循环，应把循环次数少的放在最外层，最大的循环位居最内部，以减少内层循环的执行次数。第二章 各种算法的速度一、排序算法的速度1.冒泡排序for(i=0;i<20000;i+) ai=rand();s=clock();for(i=0;i<n;i+) for(j=0;j<i;j+) if(ai>aj) t=ai; ai=aj; aj=t; b=clock();运行时间：1407ms2.选择排序for(i=0;i<20000;i+) ai=rand(); s=clock(); for(i=0;i&l

14、t;n;i+) max=0; for(j=0;j<n;j+) if(aj>amax) max=j; bi=amax; amax=-1000000; t=clock();运行时间：1220ms3.插入排序for(i=0;i<20000;i+) ai=rand(); s=clock(); for(i=0;i<n;i+) t=ai; for(j=i-1;j>=0;j-) if(aj>t) break; for(l=i;l>j+1;l-) al=al-1; aj+1=t; t=clock();运行时间：984ms以上三种都是O(n2)的排序，其中插入排序最快，

15、且可以用指针加以优化。从编程复杂度上，冒泡排序最简单。从算法的稳定性上，插入排序是稳定的，即排序后关键字相同的记录顺序不改变，特别适用于表达式处理等问题。一般的选择排序是不稳定的，但这里给出的程序由于使用了人类最原始的方法，即依次选择最大的并排除，故是稳定的。冒泡排序是不稳定的，涉及必须保持数据原顺序的题目时不能选择冒泡排序，而必须选择稳定的排序方式。以下试验所采用的环境是： CPU Intel Core 1.73GHz*2，内存512M，操作系统Windows 7 Ultimate Beta，程序语言C。编译环境Dev-c+，以下称为2号机。由于CPU速度较慢，且操作系统占用资源较多，程序运

16、行速度明显减慢，第一章的“基本运行测试”需要时间约为前者的2倍，即为406ms。故第一章的程序运行时间此处应乘2。4.快速排序的标准版#define MAX 10000000int aMAX;int p(int l,int r) int x=al,i=l-1,j=r+1,t; while(1) do-j; while(aj<x); do+i; while(ai>x); if(i<j) t=ai;ai=aj;aj=t; else return j; void q(int l,int r) int n; if(l<r) n=p(l,r); q(l,n); q(n+1,r);

17、 运行时间：2948ms。注意：不要以为三种平方级排序方法的速度与快速排序可比拟，因为平方级的数据范围是10000，而快速排序的范围是10000000。对于10000的数据，快速排序只需3.1ms。另外，快速排序不是稳定的排序，需要保持原顺序的不能用此法。void p(int l,int r) int x=al,i=l-1,j=r+1,t; if(l<r) while(1) do-j; while(aj<x); do+i; while(ai>x); if(i<j) t=ai;ai=aj;aj=t; else break; p(l,j); p(j+1,r); 若程序改为以

18、上形式，则运行时间为2917ms，稍快了一些，是因为减少了函数调用次数。对于函数调用，我们进行这样的测试。s=clock();for(i=0;i<100000000;i+) test();t=clock();int test() int n; n+;净运行时间200msint test() int n;净运行时间84msint test()净运行时间10ms由此可见，调用函数本身并不浪费时间，仅相当于循环本身时间400ms的1/40，相当于加法80ms的1/8，是很快的运算。但由于在函数内部需要进行现场保护，调用系统堆栈，所以用时大幅增加，定义变量后只是一个自增运算就用去120ms，相当

19、于主程序中加法运算时间的3/2倍。故函数中的运算比主程序中要慢，尤其是反复调用函数，会增加不必要的时间开销。所以，一些简单的功能尽量在一个函数或主程序内完成，不要使用过多的函数；涉及全局的变量不要在函数调用时由接口给出，再返回值，尽量使用全局变量。这些方法可能使程序的可读性降低，不利于调试，但有利于提高时效，正如汇编语言程序比高级语言快一样。5.优化的快速排序（1）用插入排序优化由于递归调用浪费大量时间，本算法的思想是，当首尾间距小于min时，改用效率较高的插入排序，减少反复递归。这个想法是好的，但运行效果并不如人意。当min=4时，程序运行时间降为2901ms，优化幅度不大，且增加了编程复杂

20、度，故不宜采用。其原因是递归调用、插入排序内部循环所用时间过长。（2）用小数据判断优化 if(l+1<r) while(1)/与普通快速排序相同 else if(l+1=r&&al<ar) t=ai;ai=aj;aj=t;仅就区间长度为2的情况进行判断优化，减少一次递归调用，就能使运行时间缩短为2699ms，降低了200ms以上。而区间长度不小于3的直接判断有困难。快速排序运行时间（单位：ms）数据规模10000100000100000010000000原始快速排序1.5025.20258.552716.45优化快速排序2.3023.40245.402564.806

21、.归并排序归并排序是一种稳定的排序方法，且时间效率与快速排序相同，都是O(nlogn)。但归并排序比快速排序的常数因子大，故快速排序还是最快的排序方法。归并排序则适用于有特殊要求的题目，如不满足交换律的表达式处理。int aMAX,bMAX;void combine(int from,int to) int i,t,mid=(from+to)/2,f,r; if(from=to|from+1=to) return; if(from+2=to) if(afrom<afrom+1) t=afrom; afrom=afrom+1; afrom+1=t; return; combine(from

22、,mid); combine(mid,to); f=from; r=mid; i=from; while(f!=mid|r!=to) if(f!=mid&&af>ar) bi+=af+; else bi+=ar+; for(i=from;i<to;i+) ai=bi; 调用：combine(0,MAX);归并排序算法还可用于统计逆序对数。所谓逆序对，即为在一个数组a中，满足i<j且ai>aj（或ai<aj，依排序方向而定）的点(i,j)的个数。void sort(int from,int to) int i,t,mid=(from+to)/2,f,

23、r; if(from=to|from+1=to) return; if(from+2=to) if(afrom<afrom+1) t=afrom; afrom=afrom+1; afrom+1=t; tot+; return; sort(from,mid); sort(mid,to); f=from; r=mid; i=from; while(f!=mid|r!=to) if(f!=mid&&af>ar) bi+=af+; else bi+=ar+; if(f!=mid) tot+=(mid-from); for(i=from;i<to;i+) ai=bi;

24、主函数： sort(0,n); printf("%d",n*(n-1)/2-tot);7.多关键字排序多关键字排序，经常出现于要求按某要素排序姓名，该要素相同的按字典序排列的题目。这样，此要素是第一关键字，姓名是第二关键字。qist(0,n-1);j=0;for(i=1;i<n;i+) if(istloi!=istloi-1) qnameist(j,i-1); j=i; qnameist(j,n-1);此算法的意思是，先按第一关键字快速排序，在从左至右扫描，找到每段相同的元素，再按第二关键字快速排序。此算法复杂度仍为O(nlogn)，且比两次快速排序要快，因为第二次排

25、序已用O(n)的时间将其分为若干小块，排序效率大大提高。8.字符串排序void qname(int l,int r) int i=l-1,j=r+1,t; while(1) do-j; while(strcmp(nameloj,nameloi)>0); do+i; while(strcmp(nameloj,nameloi)<0); if(i<j) t=loi;loi=loj;loj=t; else break; if(l<r) qname(l,j); qname(j+1,r);上述排序方法，实质上是将普通快速排序中的数大小比较换成字符串大小比较。为了避免字符串交换浪费时

26、间，采用了类似指针的定位数组，只需交换定位数组的元素即可。当然，用指针直接实现效率更高。关于字符串比较函数strcmp的时间效率，我们有如下试验：for(i=0;i<100;i+) ai=rand(); bi=rand();s=clock();for(i=0;i<100000000;i+) if(strcmp(a,b)=0) break;t=clock();运行时间：1046ms，其中净运行时间约640ms。这是对长度100的字符串进行108次比较的时间。故strcmp的效率即为约8次整数比较所需时间，比自己编写的函数快。int str(char a,char b) int i=0

27、; while(ai!=0|bi!=0) if(ai>bi) return 1; if(ai<bi) return -1; return 0; 运行时间：1131ms，净运行时间约725ms，相当于9次整数比较时间，比标准库函数稍慢。显然，标准库函数是经过精心优化的，我们在有库函数可用时尽量用库函数，不仅降低编程复杂度，降低错误率，还能提高时间效率。9.Hash排序#define MOD 999997/As a big prime#define MAX 10000/As the max length of the stringint ELFhash(char *key) unsig

28、ned long h=0; while(*key) h=(h<<4)+*key+; unsigned long g=h&0Xf0000000L; if(g) h=g>>24; h&=g; return h%MOD;Hash排序，就是先对读入的字符串求Hash值。第一种方案是，再对Hash值进行快速排序，最后应用二分搜索查找。此时无需MOD大质数。第二种方案是，将Hash值MOD后，放入Hash表中，并用开散列等方法处理冲突。显然，第二种方案更优，但编程复杂度也较高。综上所述，在选择适当的排序算法时，要注意时间复杂度和编程复杂度，同时保证满足题意。二、最短

29、路算法的比较在图论中，最短路算法是常见的。对于常见的几种算法，到底哪种更优，还是各有千秋？我们不妨一试。以下实验在1号机上进行，均为试验20次随机数取平均值的结果。1.单源最短路径dijkstra算法void dijkstra() int i,j,min=0; for(i=0;i<n;i+) disi=d0i; for(i=1;i<n;i+) min=n; for(j=0;j<n;j+) if(!usej&&dij<dimin) min=j; usemin=1; for(j=0;j<n;j+) if(dismin+dminj<disj) di

30、sj=dismin+dminj; 随机数产生器：for(i=0;i<MAX;i+) for(j=0;j<MAX;j+) if(i!=j) dij=rand();当MAX=2000时（即点数为2000个），运行时间：28.2ms。当MAX更大时，内存会使用过多，故在1s时限内至多运行规模为2000的单源最短路径35次。2.单源最短路径Ford算法int ford() int i,j; for(i=1;i<n;i+) di=MAXINT; for(i=1;i<n;i+) for(j=0;j<num;j+) if(dfj+wj<dej) dej=dfj+wj; f

31、or(j=0;j<num;j+) if(dfj+wj<dej) return 0; return 1; 数据构造：10*n条随机边。当n=1000时，运行时间：49.95ms。当n=10000时，运行时间：6766ms。数据构造：n*n条边的完全图。当n=1000时，运行时间6469ms。比Dijkstra和SPFA都慢很多，因为其算法的理论时间复杂度就达到了O(VE)，属于介于O(n2)与O(n3)的算法。但我们仍然需要这种算法，因为当图中存在负权时，必须使用Ford算法。同时，该算法还能判断图中是否存在负权回路（无解）。3.单源最短路径SPFA算法struct mising i

32、nt num; int poo; struct mising *p; ;int wor500000;int dis60001;int yes60001=0;int beg=0,end=1;main() int n,m; int a,b,c,i; struct mising q60001,*qq60001,*x; double s,t; FILE *fp; fp=fopen("1.txt","r"); fscanf(fp,"%d%d",&n,&m); for(i=0;i<n;i+) qqi=&qi; for

33、(i=0;i<m;i+) fscanf(fp,"%d%d%d",&a,&b,&c); a-; b-; qqa->p=(struct mising *)malloc(sizeof(struct mising); qqb->p=(struct mising *)malloc(sizeof(struct mising); qqa=qqa->p; qqb=qqb->p; qqa->poo=b; qqb->poo=a; qqa->num=qqb->num=c; s=clock(); for(i=0;i<

34、;n;i+) qqi->p=NULL; disi=-1; yes0=1; wor0=0; dis0=0; while(beg!=end) x=qworbeg.p; while(x!=NULL) if(disx->poo=-1|(disx->poo>x->num+disworbeg&&disx->poo!=-1) disx->poo=disworbeg+x->num; worend=x->poo; if(yesx->poo=0) yesx->poo=1; end+; x=x->p; yesworbeg=0;

35、beg+; printf("%d",disn-1); t=clock();随机数生成模块： fprintf(fp,"%d %dn",n,10*n); for(i=0;i<10*n;i+) j=rand()%n+1; k=rand()%n+1; while(j=k) j=rand()%n+1; k=rand()%n+1; fprintf(fp,"%d %d %dn",j,k,rand(); 运行时间（不含文件操作）：当n=100000时，运行时间1937ms；当n=10000时，运行时间141ms；当n=1000时，运行时间小于1

36、0ms。特别需要注意的是，当n=50000时，用时828ms，再加上文件操作用时，可称为是SPFA算法数据规模的上限。这组数据是n个点，10*n条随机边的情况下作出的。若使用O(n2)的Dijkstra算法，时间将大幅增加。对于单源最短路径，要考虑题意要求，稀疏图使用SPFA，密集图使用Dijkstra，以提高运行效率。3.点对点最短路径Floyed算法void floyed() int i,j,k,min=0; for(k=0;k<n;k+) for(i=0;i<n;i+) for(j=0;j<n;j+) if(dik+dkj<dij) dij=dik+dkj;当MA

37、X=500时，运行时间：979.85ms。这提示我们，点对点最短路径的规模最大为500，否则会超时。若使用MAX-1次dijkstra算法void dijkstra() int i,j,k,min=0; for(k=0;k<n-1;k+) int useMAX=0; for(i=0;i<n;i+) disi=dki; for(i=1;i<n;i+) min=n; for(j=0;j<n;j+) if(!usej&&dij<dimin) min=j; usemin=1; for(j=0;j<n;j+) if(dismin+dminj<di

38、sj) disj=dismin+dminj; 当MAX=500时，运行时间：1625ms，与floyed的980ms相比，显然慢了很多。因此，floyed算法是点对点最短路径的“正统”算法。三、字符串匹配算法的比较1.朴素匹配算法for(i=0;i<1000;i+) Si=1; for(j=0;j<100000;j+) Tj=1; s=clock(); tot=0; ls=strlen(S); lt=strlen(T); for(i=0;i<lt-ls;i+) for(j=0;j<ls;j+) if(Ti+j!=Sj) break; if(j=ls) tot+; pri

39、ntf("%d ",tot); t=clock();运行时间：335.35ms。这组测试数据是：原串100000个1，匹配串1000个1.若使用更极端的数据，如匹配串10000个1，则需要数秒出解，显然过慢。对于随机数据，由于匹配的可能性极小，用时很快是必然的。我们只考虑极端数据。2.KMP算法（优化）int KMP() int i,q=0; for(i=1;i<=ls;i+) while(q>0&&Tq+1!=Si) q=nextq; if(Tq+1=Si) q+; if(q=lt) atot+=i-lt+1; void ff() int q,

40、k; for(q=1;q<=lt;q+) k=nextq; while(k>0&&Tk+1=Tq+1) k=nextk; nextq=k; void f() int q,k; next1=0;k=0; for(q=2;q<=lt;q+) while(k>0&&Tk+1!=Tq) k=nextk; if(Tk+1=Tq) k=k+1; nextq=k; 调用过程： f(); ff(); KMP();算法说明：函数f计算初始“回复位置”，函数ff计算优化后的“回复位置”，函数KMP是依赖上述“回复位置”进行快速匹配的算法。Si为待匹配串，Ti

41、为目标串，nexti计算“回复位置”。运行时间：当目标串长1000，匹配串长100000时0.8ms。目标串长100时2.3ms。目标串长10或10000时，运行时间1.55ms。可见，KMP算法极快，确实是O(n)的时间复杂度。故正确的优化KMP算法是不会超时的。同样，优化KMP与普通KMP的差距也很明显，尤其是在极端数据时。四、最小生成树算法的比较1.Prim算法void prim() int lowcost2002,closet2002,i,j,k,min,tot=0; for(i=1;i<=n;i+) lowcosti=cost1i; closeti=1; for(i=1;i&l

42、t;n;i+) min=MAXINT; for(j=1;j<=n;j+) if(lowcostj<min&&lowcostj!=0) min=lowcostj; k=j; tot+=lowcostk; lowcostk=0; for(j=1;j<=n;j+) if(costkj<lowcostj) lowcostj=costkj; closetj=k; printf("%d ",tot);随机数生成：for(i=1;i<=MAX;i+) for(j=1;j<=MAX;j+) if(i!=j) costij=rand();当

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

44、 int i,j,start,end,value,cost=0; for(i=0;i<n;i+) seti=i; for(k=1;k<n;k+) value=MAXINT; for(i=0;i<n;i+) for(j=0;j<n;j+) if(i!=j&&father(i)!=father(j) if(dataij<value) start=i; end=j; value=dataij; cost+=value; setfather(start)=father(end); printf("%d ",cost);当规模MAX=50

45、0时，运行时间：3563ms。显然，当图为密集矩阵时，Kruskal算法并不迅速。但当图为稀疏图时，算法的优势便很明显了。3.Kruskal算法（优化）int find(int x) if(fx!=x) fx=find(fx); return fx;void kruskal() int i,j,a,b,tot=0,num=0; for(i=0;i<n;i+) fi=i; for(i=0;i<n;i+) a=find(si); b=find(ei); if(a!=b) num+; tot+=wi; fa=b; if(num=max) break; printf("%d &q

46、uot;,tot);主程序：for(i=1;i<n;i+) fi=rand()%max; ei=rand()%max; wi=rand(); s=clock(); sort(0,n-1); kruskal(); t=clock();此处sort函数是快速排序函数，采用了本文上述“优化的快速排序算法”。当max=100000时，即共100000个点，共1000000条边时，平均运行时间为409.4ms。当max=10000时，平均运行时间为43.7ms。完全满足时限1s的要求。而若使用O(n2)的Prim算法，运行时间将不可思议。故Kruskal算法十分适合稀疏图的处理。我们再来看Krus

47、kal算法对于密集图的效率。for(i=0;i<max;i+) for(j=0;j<max;j+) fi=i; ei=j; wi=rand(); 当max=2000时，平均运行时间1394.5ms，比Prim的47ms慢了约30倍。通过单独测试sort时间可知，当数目过多时，快速排序占去很多的时间（平均1299.3ms），而Kruskal算法本身仍然很快（不到100ms）。综上所述，在解题前，务必看清题中给出的图是密集图还是稀疏图，并选择合适的算法，否则程序运行速度会很慢。五、拓扑排序算法int tuopu() int i,j,k; for(i=0;i<n;i+) for(j

48、=0;j<n;j+) if(aij) dj+; for(i=0;i<n;i+) for(j=0;j<n;j+) if(dj=0) break; if(j=n) return 0; dj=-1; ansi=j; for(k=0;k<n;k+) if(ajk) ajk=0; dk-; return 1;取随机数据测试：当n=1000时，运行时间：15ms；当n=2000时，运行时间：63ms。当n过大时，数组将越界。六、搜索算法的比较1.朴素深度优先搜索程序框架：（函数依具体题目而定）void op(int now)void read()void print()void printerror()int ans(int now)int s(int now) int i,flag; if(now=n) if(ans(now) return 1; return 0; for(i=0;i<n;i+) op(i); flag=s(