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

鄂教版信息技术九下第9课程序调试优化算法内容摘要：

b]=qq[b]p。 qq[a]poo=b。 qq[b]poo=a。 qq[a]num=qq[b]num=c。 } s=clock()。 for(i=0。 in。 i++) { qq[i]p=NULL。 dis[i]=1。 } yes[0]=1。 wor[0]=0。 dis[0]=0。 while(beg!=end) { x=q[wor[beg]].p。 while(x!=NULL) { if(dis[xpoo]==1||(dis[xpoo]xnum+dis[wor[beg]]amp。 amp。 dis[xpoo]!=1)) { dis[xpoo]=dis[wor[beg]]+xnum。 wor[end]=xpoo。 if(yes[xpoo]==0) { yes[xpoo]=1。 end++。 } } x=xp。 } yes[wor[beg]]=0。 beg++。 } printf(%d,dis[n1])。 t=clock()。 随机数生成模块： fprintf(fp,%d %d\n,n,10*n)。 for(i=0。 i10*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 %d\n,j,k,rand())。 } 运行时间（不含文件操作）：当 n=100000时，运行时间 1937ms；当 n=10000时，运行时间 141ms；当 n=1000时，运行时间小于 10ms。 特别需要注意的是，当 n=50000时，用时828ms，再加上文件操作用时，可称为是 SPFA算法数据规模的上限。 这组数据是 n 个点，10*n条随机边的情况下作出的。 若使用 O(n^2)的 Dijkstra算法，时间将大幅增加。 对于单源最短路径，要考虑题意要求，稀疏图使用 SPFA，密集图使用 Dijkstra，以提高运行效率。 —— Floyed算法 void floyed() { int i,j,k,min=0。 for(k=0。 kn。 k++) for(i=0。 in。 i++) for(j=0。 jn。 j++) if(d[i][k]+d[k][j]d[i][j]) d[i][j]=d[i][k]+d[k][j]。 } 当 MAX=500 时，运行时间：。 这提示我们，点对点最短路径的规模最大为500，否则会超时。 若使用 MAX1次 dijkstra算法 void dijkstra() { int i,j,k,min=0。 for(k=0。 kn1。 k++) { int use[MAX]={0}。 for(i=0。 in。 i++) dis[i]=d[k][i]。 for(i=1。 in。 i++) { min=n。 for(j=0。 jn。 j++) if(!use[j]amp。 amp。 d[i][j]d[i][min]) min=j。 use[min]=1。 for(j=0。 jn。 j++) if(dis[min]+d[min][j]dis[j]) dis[j]=dis[min]+d[min][j]。 } } } 当 MAX=500时，运行时间： 1625ms，与 floyed的 980ms相比，显然慢了很多。 因此，floyed算法是点对点最短路径的“正统”算法。 三、字符串匹配算法的比较 for(i=0。 i1000。 i++) S[i]=1。 for(j=0。 j100000。 j++) T[j]=1。 s=clock()。 tot=0。 ls=strlen(S)。 lt=strlen(T)。 for(i=0。 iltls。 i++) { for(j=0。 jls。 j++) if(T[i+j]!=S[j]) break。 if(j==ls) tot++。 } printf(%d ,tot)。 t=clock()。 运行时间：。 这组测试数据是：原串 100000个 1，匹配串 1000个 1. 若使用更极端的数据，如匹配串 10000个 1，则需要数秒出解，显然过慢。 对于随机数据，由于匹配的可能性极小，用时很快是必然的。 我们只考虑极端数据。 算法（优化） int KMP() { int i,q=0。 for(i=1。 i=ls。 i++) { while(q0amp。 amp。 T[q+1]!=S[i]) q=next[q]。 if(T[q+1]==S[i]) q++。 if(q==lt) a[tot++]=ilt+1。 } } void ff() { int q,k。 for(q=1。 q=lt。 q++) { k=next[q]。 while(k0amp。 amp。 T[k+1]==T[q+1]) k=next[k]。 next[q]=k。 } } void f() { int q,k。 next[1]=0。 k=0。 for(q=2。 q=lt。 q++) {while(k0amp。 amp。 T[k+1]!=T[q]) k=next[k]。 if(T[k+1]==T[q]) k=k+1。 next[q]=k。 } } 调用过程： f()。 ff()。 KMP()。 算法说明：函数 f计算初始“回复位置”，函数 ff计算优化后的“回复位置”，函数 KMP是依赖上述“回复位置”进行快速匹配的算法。 S[i]为待匹配串， T[i]为目标串， next[i]计算“回复位置”。 运行时间：当目标串长 1000，匹配串长 100000 时。 目标串长 100 时。 目标串长 10 或 10000时，运行时间。 可见， KMP 算法极快，确实是 O(n)的时间复杂度。 故正确的优化 KMP 算法是不会超时的。 同样，优化 KMP与普通 KMP的差距也很明显，尤其是在极端数据时。 四、最小生成树算法的比较 void prim() { int lowcost[2020],closet[2020],i,j,k,min,tot=0。 for(i=1。 i=n。 i++) { lowcost[i]=cost[1][i]。 closet[i]=1。 } for(i=1。 in。 i++) { min=MAXINT。 for(j=1。 j=n。 j++) if(lowcost[j]minamp。 amp。 lowcost[j]!=0) { min=lowcost[j]。 k=j。 } tot+=lowcost[k]。 lowcost[k]=0。 for(j=1。 j=n。 j++) if(cost[k][j]lowcost[j]) { lowcost[j]=cost[k][j]。 closet[j]=k。 } } printf(%d ,tot)。 } 随机数生成： for(i=1。 i=MAX。 i++) for(j=1。 j=MAX。 j++) if(i!=j) cost[i][j]=rand()。 当数据范围 MAX=2020时，平均 运行时间：。 由于 Prim算法是 O(n^2)的，速度快不是偶然。 由此可见，最小生成树不是程序运行时间的瓶颈。 从算法上看，我们注意到 Prim 算法十分类似求单源最短路径的 Dijkstra 算法。 两种算法都是先找出不在集合中的最近元素，将其加入集合，并对该元素连接的点进行松弛操作，更新各点到集合的距离。 在具体实现中，都是利用一个数 组记录每个点到集合的距离， 点在集合中用距离为零表示。 （较差） int father(int x) { if(set[x]!=x) set[x]=father(set[x])。 return set[x]。 } void kruskal() { int i,j,start,end,value,cost=0。 for(i=0。 in。 i++) set[i]=i。 for(k=1。 kn。 k++) { value=MAXINT。 for(i=0。 in。 i++) for(j=0。 jn。 j++) if(i!=jamp。 amp。 father(i)!=father(j)) if(data[i][j]value) { start=i。 end=j。 value=data[i][j]。 } cost+=value。 set[father(start)]=father(end)。 } printf(%d ,cost)。 } 当规模 MAX=500时，运行时间： 3563ms。 显然，当图为密集矩阵时， Kruskal算法并不迅速。 但当图为稀疏图时，算法的优势便很明显了。 （优化） int find(int x) { if(f[x]!=x) f[x]=find(f[x])。 return f[x]。 } void kruskal() { int i,j,a,b,tot=0,num=0。 for(i=0。 in。 i++) f[i]=i。 for(i=0。 in。 i++) { a=find(s[i])。 b=find(e[i])。 if(a!=b) { num++。 tot+=w[i]。 f[a]=b。 if(num==max) break。 } } printf(%d ,tot)。 } 主程序： for(i=1。 in。 i++) { f[i]=rand()%max。 e[i]=rand()%max。 w[i]=rand()。 } s=clock()。 sort(0,n1)。 kruskal()。 t=clock()。 此处 sort函数是快速排序函数，采用了本文上述“优化的快速排序算法”。 当 max=100000时，即共 100000个点，共 1000000条边时，平均运行时间为。 当 max=10000 时，平均运行时间为。 完全满足时限 1s 的要求。 而若使用 O(n^2)的Prim算法，运行时间将不可思议。 故 Kruskal算法十分适合稀疏图的处理。 我们再来看 Kruskal算法对于密集图的效率。 for(i=0。 imax。 i++) for(j=0。 jmax。 j++) { f[i]=i。 e[i]=j。 w[i]=rand()。 } 当 max=2020时，平均运行时间 ，比 Prim的 47ms慢了约 30倍。 通过单独测试 sort 时间可。