}
主程序： sum=0;
upperlim=(1< 由此可见，对搜索问题，优化的空间还是很大的。 3.广度优先搜索 广度优先搜索的时间复杂度从理论上说，搜索完整棵树与深度优先搜索的相同，只是适用范围不同。两者的根本区别在于，实现方式一个是栈，先进先出；一个是队列，先进后出。主要的瓶颈是空间问题，数组不能太大，必要时使用循环队列解决。 程序框架：（函数依具体问题而定） void read(){} void print(){}//print last a[] as the answer int op(){}//return result made depending on last a[] int ans(){}//test last a[] if it is the answer void s(int from) { int i,t=num; for(i=from;i a[num++]=op(); } s(t); } main() { read(); s(0); print(); } 以图论中的“种子填充法”为例：（计算某点开始的连通图形面积） #include int n,m,a[1000][1000]={0},x[1000][1000]={0}; int fill(int i,int j) { int tot=1; if(a[i][j]==0||x[i][j]==1) return 0; x[i][j]=1; tot+=fill(i-1,j); tot+=fill(i+1,j); tot+=fill(i,j-1); tot+=fill(i,j+1); return tot; } main() { int i,j,tot=0; scanf(\ for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf(\ for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(x[i][j]==0&&a[i][j]==1) printf(\ getch(); } 当n=1000时，随机数实验表明，平均运行时间为14.1ms。（当心系统堆栈溢出！）事实上，由于前面填充时已经填入大部分点，则采用记忆化搜索的办法，同在一个区域中的点不必重新搜索，故算法效率仍为O(n^2)。 4.线性搜索（二分法） int search(int from,int to,int x) { if(a[(from+to)/2]==x) return (from+to)/2; if(from==to||from+1==to) return -1; if(a[(from+to)/2] return search((from+to)/2,to,x); return search(from,(from+to)/2,x); } 主函数：（重复1000000次，便于测量时间，此时循环时间可忽略） for(i=0;i<1000000;i++) search(0,n,i); 当n=100时，运行时间：141.15ms。当n=1000时，运行时间：195.75ms。当n=10000时，运行时间267.5ms。当n=100000时，运行时间：335.4ms。当n=1000000时，运行时间：386.85ms。上述数据可供实际编程时估计运行时间。即使对于n=10000000的极限数据，运行时间也只有467.85ms。可见二分搜索的时间复杂度相当稳定，确实成对数级变化，对n不太敏感。而下面的优化算法，更使极限大数据10000000的耗时缩减到300ms左右，而小数据的速度则突破了100ms。 我们对上述二分搜索算法进行优化。 int search(int from,int to,int x) { int t=(from+to)>>1; if(a[t]==x) return t; if(from>=to) return -1; if(a[t]>x) return search(from,t-1,x); return search(t+1,to,x); } 朴素二分搜索算法与优化二分搜索算法比较表（运行次数：1000000，单位：ms） 数据规模 朴素算法 优化算法 100 141.15 84.20 1000 195.75 122.45 10000 267.50 170.80 100000 335.40 215.25 1000000 386.85 255.85 10000000 467.85 308.85 由上表可见，仅仅是对常数级别的一个优化，带来了程序运行时间上如此大的差别。所以我们在编写程序时，一定要注意细节上的优化，避免超时。尤其对于一些搜索类题目，一个合理的剪枝、函数中细节的设计可能大大提高程序的得分。 上述算法将重复出现的(from+to)/2替换成一个变量t，避免重复计算，并运用较快的位运算代替较慢的除法。可见当一个表达式重复出现时，用一个变量整体代换，并用位运算<<1, >>1, &1代替*2，/2，%2的运算，可以大幅提高常数级运行速率。整体代换思想的实质是，不做重复性工作，充分利用已有成果。 而对朴素算法（一一查找）： for(i=0;i<1000000;i++) for(j=0;j 当n=100时，运行时间：4664ms，慢得令人难以忍受。当n更大时，时间呈线性增加，不再一一列举。 七、最长上升子序列算法 1.朴素动态规划算法 for(i=0;i s=clock(); for(i=0;i if(a[i]>a[j]&&f[j]+1>f[i]) f[i]=f[j]+1; max=0; for(i=0;i printf(\ e=clock(); 朴素动态规划算法运行时间：（20次取平均值，单位：ms） 数据规模 1000 10000 随机数据 递增数据 递减数据 5.45 4.65 3.10 517.95 468.75 246.05 由上表，可知动态规划算法极慢，且较为稳定，对有序数据不敏感。 2.二分搜索算法 int bsearch(int f[],int size,int a) { int l=0,r=size-1,m; while (l<=r) { m=(l+r)/2; if (a>f[m-1] && a<=f[m]) return m; else if(a 主程序： s=clock(); f[0]=a[0];size=1; for (i=1;i else if (a[i]>f[size-1]) j=size; else j=bsearch(f,size,a[i]); f[j]=a[i]; if (j==size) size++; } printf(\ e=clock(); 二分搜索算法运行时间：（20次取平均值，单位：ms） 数据规模 随机数据 递增数据 递减数据 10000 1.55 0 0 100000 19.5 1.6 0 1000000 226.8 11.75 8.65 10000000 2672 125 78.15 由上表可见，二分搜索算法的效率极高，尤其在接近有序的极端数据时更有优势。 注意：上述两表的数据规模不同，表1最大为10000，表2最大为10000000。 所以，在求最长上升（下降）子序列时一定要采用O(nlogn)的高效算法。同样，最长公共子序列问题可在O(n)的时间内转化为上述问题，同样可快速求解。 八、最大子长方体算法（包括最大子矩阵、最大字段和） 1.最朴素算法——O(n^9) for(i=0;i<=h;i++) for(j=0;j<=m;j++) for(k=0;k<=n;k++) for(p=i;p<=h;p++) for(q=j;q<=m;q++) for(r=k;r<=n;r++) { now=0; for(u=i;u<=p;u++) for(v=j;v<=q;v++) for(w=k;w<=r;w++) now+=a[u][v][w]; if(now>max) max=now; } printf(\ 2.记录子长方体和，应用容斥原理——O(n^6) for(i=1;i<=h;i++) for(j=1;j<=m;j++) for(k=1;k<=n;k++) { scanf(\ b[i][j][k]=t+b[i-1][j][k]+b[i][j-1][k]+b[i][j][k-1]+b[i-1][j-1][k-1]-b[i-1][j-1][k]-b[i-1][j][k-1]-b[i][j-1][k-1]; } for(i=0;i<=h;i++) for(j=0;j<=m;j++) for(k=0;k<=n;k++) for(p=i;p<=h;p++) for(q=j;q<=m;q++) for(r=k;r<=n;r++) { t=b[p][q][r]-b[i][q][r]-b[p][j][r]-b[p][q][k]-b[i][j][k]+b[i][j][r]+b[i][q][k]+b[p][j][k]; if(t>max) max=t; } 3.最优化算法，充分利用已有数据——O(n^5) #include int b[52][52][52]={0},a[52][52][52]={0},f[52][52]={0},g[52][52]={0},c[52]={0}; int main() { int m,n,h,i,j,k,p,q,r,t,max=0,tmp; scanf(\ for(i=1;i<=h;i++) for(j=1;j<=m;j++) for(k=1;k<=n;k++) { scanf(\ a[i][j][k]=a[i-1][j][k]+t; } for(i=0;i<=h;i++) for(j=i+1;j<=h;j++)