算法效率与程序优化(4)

是依赖上述“回复位置”进行快速匹配的算法。S[i]为待匹配串，T[i]为目标串，next[i]计算“回复位置”。

运行时间：当目标串长1000，匹配串长100000时0.8ms。目标串长100时2.3ms。目标串长10或10000时，运行时间1.55ms。可见，KMP算法极快，确实是O(n)的时间复杂度。故正确的优化KMP算法是不会超时的。同样，优化KMP与普通KMP的差距也很明显，尤其是在极端数据时。

四、最小生成树算法的比较 1.Prim算法 void prim()

{ int lowcost[2002],closet[2002],i,j,k,min,tot=0; for(i=1;i<=n;i++)

{ lowcost[i]=cost[1][i]; closet[i]=1; }

for(i=1;i

if(lowcost[j]

tot+=lowcost[k]; lowcost[k]=0; for(j=1;j<=n;j++)

if(cost[k][j]

printf(\}

随机数生成：

for(i=1;i<=MAX;i++)

for(j=1;j<=MAX;j++) if(i!=j)

cost[i][j]=rand();

当数据范围MAX=2000时，平均运行时间：46.95ms。

由于Prim算法是O(n^2)的，速度快不是偶然。由此可见，最小生成树不是程序运行时间的瓶颈。从算法上看，我们注意到Prim算法十分类似求单源最短路径的Dijkstra算法。两种算法都是先找出不在集合中的最近元素，将其加入集合，并对该元素连接的点进行松弛操作，更新各点到集合的距离。在具体实现中，都是利用一个数组记录每个点到集合的距离，点在集合中用距离为零表示。

2.Kruskal算法（较差）

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;i

for(k=1;k

if(i!=j&&father(i)!=father(j)) if(data[i][j]

value=data[i][j]; }

cost+=value;

set[father(start)]=father(end); }

printf(\}

当规模MAX=500时，运行时间：3563ms。显然，当图为密集矩阵时，Kruskal算法并不迅速。但当图为稀疏图时，算法的优势便很明显了。

3.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;i

for(i=0;i

if(num==max)

break; } }

printf(\}

主程序：

for(i=1;i

{ f[i]=rand()%max; e[i]=rand()%max; w[i]=rand(); }

s=clock(); sort(0,n-1); kruskal(); t=clock();

此处sort函数是快速排序函数，采用了本文上述“优化的快速排序算法”。

当max=100000时，即共100000个点，共1000000条边时，平均运行时间为409.4ms。当max=10000时，平均运行时间为43.7ms。完全满足时限1s的要求。而若使用O(n^2)的Prim算法，运行时间将不可思议。故Kruskal算法十分适合稀疏图的处理。

我们再来看Kruskal算法对于密集图的效率。 for(i=0;i

for(j=0;j

w[i]=rand(); }

当max=2000时，平均运行时间1394.5ms，比Prim的47ms慢了约30倍。通过单独测试sort时间可知，当数目过多时，快速排序占去很多的时间（平均1299.3ms），而Kruskal算法本身仍然很快（不到100ms）。

综上所述，在解题前，务必看清题中给出的图是密集图还是稀疏图，并选择合适的算法，否则程序运行速度会很慢。

五、拓扑排序算法 int tuopu() { int i,j,k;

for(i=0;i

for(i=0;i

return 0; d[j]=-1; ans[i]=j;

for(k=0;k

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

flag=s(now+1); if(flag) return 1; }

return 0; }

main() { int flag; read(); flag=s(0); if(flag) print();

else printerror();

return; }

以经典的“八皇后问题”为例。 void queen(int x,int y) { int i,a,b; if(x==n-1) { tot++; return; }

for(i=x;i

while(a=0) use[a++][b--]=1; for(i=0;i

while(a=0) use[a++][b--]=0; }

当n<=8时，速度无法测出。当n=9时，用时109ms。当n=10时，用时2406ms。可见，朴素的回溯算法在八皇后问题中，所用时间随N的增大而迅速增大，复杂度几乎为N！。

2.位运算

void test(long row,long ld,long rd) { long p,pos;

if(row!=upperlim)

{ pos=upperlim&~(row|ld|rd); while(pos) {

p=pos&(-pos); pos-=p;

test(row+p,(ld+p)<<1,(rd+p)>>1); } }

else sum++;