算法效率与程序优化

算法效率与程序优化

在信息学竞赛中，常遇到程序运行超时的情况。然而，同一个程序设计思想，用不同算法，会有不同的运行效率；而即使是同样的算法，由于在代码的细节方面设计有所不同，执行起来效率也会有所不同。当遇到所需时间较长的问题时，一个常数级优化可能是AC的关键所在。下面，我们就从代码细节与算法设计两方面，比较不同程序执行时间的异同，从而选择其中较优的算法，提高程序运行效率。

本试验所采用的环境是： CPU Celeron 3.06GHz，内存248M，操作系统Windows XP SP2，程序语言C。编译环境Dev-c++。以下称为1号机。配置略好于NOIP标准测试机CPU 2.0GHz。

第一章 各种运算的速度

一、基本运算的速度

为了增强算法效率的计算准确性，我们采用重复试验20次取平均值的做法。每次试验运行100000000次。

基本运行时间，是指在准备计算的运算复杂度之外，只包括循环控制变量的加减与比较所消耗的时间。要从实际运行时间中减去基本运行时间，才是这种运算真正的运行时间，称为净运行时间。

#include 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();

printf(\ sum+=b-a; }

printf(\ getch(); }

运行平均时间是：202.3ms。 （1）赋值运算

净运行时间0.8ms，与基本运行时间202.3ms相比，可忽略不计，故以后将赋值运算作为基本运行时间的一部分，不予考虑。 （2）加法运算 产生随机数： x=rand();

y=rand();

循环内加法： t=x+y;

下面的各种简单运算只是更改运算符即可，不再写出代码。 净运行时间41.45ms，即：在1s的时限中，共可进行 (1000-202.3)/ 41.45*10^8=1.9*10^9次加法运算，即：只通过循环、加法和赋值的运算次数不超过1.9*10^9.。

而应用+=运算，与普通加法时间几乎相同，所以+=只是一种方便书写的方法，没有实质效果。同样的，各种自运算并不能提高效率。 （3）减法运算

净运行时间42.95ms，与加法运算基本相同。可见，在计算机内部实现中，把减法变成加法的求补码过程是较快的，而按位相加的过程占据了较多的时间，借用化学中的一句术语，可以称为整个运算的“速控步”。当然，这个“速控步”的运行速度受计算机本身制约，我们无法优化。在下面的算法设计中，还会遇到整个算法的“速控步”，针对这类情况，我们要对占用时间最多的步骤进行细心优化，减少常数级运算次数。

（4）乘法运算

净运行时间58.25ms，明显比加减法要慢，但不像某些人想象的那样慢，至少速度大于加减法的1/2。所以在实际编程时，没有必要把两个或三个加法变成乘法，其实不如元素乘常数来得快。不必“谈乘色变”，实际乘法作为CPU的一种基本运算，速度还是很快的。

以上四种运算速度都很快，比循环所需时间少很多，在普通的算法中，每个最内层循环约含有4-5个加、减、乘运算，故整个算法的运行时间约为循环本身所需时间的2倍。

（5）除法运算

净运行时间1210.2ms，是四种常规运算中最慢的一种，耗时是加法的28倍，是乘法的21.5倍，确实如常人所说“慢几十倍”，一秒的时限内只能运行8.26*10^7次，不足一亿次，远大于循环时间。所以，在计算时应尽量避免除法，尤其是在对时间要求较高的内层循环，尽量不安排除法，如果整个循环中值不变，可以使用在循环外预处理并用一个变量记录，循环内再调用该变量的方法，可以大大提高程序运行效率。

（6）取模运算

净运行时间1178.15ms，与除法运算速度几乎相当，都非常慢。所以，取模运算也要尽量减少。在大数运算而只要求求得MOD N的值的题目中，应尽量利用数据类型的最大允许范围，在保证不超过MAXINT的前提下，尽量少执行MOD运算。例如在循环数组、循环队列的应用中，取模运算必不可少，这时优化运算便十分重要。可利用计数足够一定次数后再统一MOD，循环完后再MOD，使用中间变量记录MOD结果等方法减少次数。

在高精度计算中，许多人喜欢边运算边整理移位，从而在内层循环中有除、模运算各一次，效率极低。应该利用int的数据范围，先将计算结果保存至当前位，在各位的运算结束后再统一整理。

以下是用统一整理法编写的高精度乘法函数，规模为10000位。 int a[10000]={0},b[10000]={0},c[10000]={0}; void mul() { int i,j,t;

for(i=0;i<10000;i++) for(j=0;j<10000-i;j++) c[i+j]+=a[i]*b[j]; for(i=0;i<9999;i++) { c[i+1]+=c[i]/10; c[i]%=10;

} }

以上函数运行后，平均用时276.55ms。 以下是边运算边整理的程序。 void mul() { int i,j,t;

for(i=0;i<10000;i++) for(j=0;j<10000-i;j++)

{ c[i+j+1]+=(c[i+j]+a[i]*b[j])/10; c[i+j]=(c[i+j]+a[i]*b[j]); } }

以上函数运行后，平均用时882.80ms。统一整理与边整理边移位相比，快了3.2倍，有明显优势。故尽量减少除法、取模运算的次数，是从常数级别降低时间复杂度的方法。

（7）大小比较 if(x>y) x=y;

净运行时间39.1ms，与加法运算速度相当。故比较运算也属于较快的基本运算。 二、位运算的速度 （1）左移、右移 x<<1; x>>1;

净运行时间无法测出，证明位运算速度极快。而使用自乘计算需要64.1ms，自除运算需要164.85ms，所以尽可能使用位运算代替乘除。

（2）逻辑运算 t=x|y; t=x^y; t=x&y;

净运行时间约30ms，比加法运算（约40ms）快较多，是因为全是按二进制位计算。但加减与位运算关系并不大，所以利用位运算主要是利用左右移位的高速度。

三、数组运算的速度 （1）直接应用数组 for(i=0;i<10000;i++)

for(k=0;k<10000;k++) t=q[k];

净运行时间39.85ms。这里计算了内层循环的时间。若改为 for(i=0;i<100000000;i++) t=q[0];

则净运行时间为1.50ms，很快，与202.3ms的循环时间相比，可以忽略。故应用数组，速度很快，不必担心数组寻址耗时。同时我们发现，循环耗时在各种运算中是很大的，仅次于乘除，故我们要尽量减少循环次数，能在一个循环中解决的问题不放在两个循环中，减少循环变量次数。

（2）二维数组 for(i=0;i<5000;i++) for(k=0;k<5000;k++) t=z[i][k];

实际运行时间为80.45ms，若规模扩至10000则10s内无法出解，由于频繁访问虚拟内存。可以试想，若物理内存足够大，则运行时间约为320ms，仅为202.3ms的基准运行时间

的3/2，差距似乎并不是很大；由此推得其净运行时间约为120ms。但相较加、减等简单操作，速度仍为3倍，尤其与几乎不需时间的一维数组相比差距巨大。尤其是在计算中，二维数组元素经常调用，时间效率不可忽视。所以，对于已知数目不多的同样大小的数组，可用几个变量名不同的一维数组表示，如x、y方向，两种不同参数，而不要滥用二维数组。在滚动数组中，可用两个数组交替计算的方式，用二维数组同样较慢。

四、实数运算的速度

测试方法与“基本运算”类似。（次数：100000000，单位：ms） 运算符 long int int64 double = 43.05 41.45 46.15 + 31.3 14.95 10.25 - -74.75 7.9 12.6 * 69.55 566.4 33.65 / 299.65 1243.45 1753.55 % 360.5 1858.85 -- 由上表可见，涉及乘除、取模时int64很慢，要慎用；int显然最快，但对大数据要小心越界。若一组变量中既有超出int的，又有不超过int的，则要分类处理，不要直接都定义成int64，尤其在乘除模较多的高精度过程中。

以上讨论了主要基本运算的速度问题。概括起来说，除、模最慢，二维数组较慢，加减乘、逻辑位运算、比较大小较快，左右移位、一维数组、赋值几乎不需要时间。而循环for或while语句十分特殊，它的运算速度大于判断大小、自加控制变量所用时间之和，无论采用内部if判断退出，还是在入口处判断，都回用去约200ms的时间。所以尽量减少循环次数，是优化算法的关键。对于双层或多层的循环，应把循环次数少的放在最外层，最大的循环位居最内部，以减少内层循环的执行次数。

第二章 各种算法的速度

一、排序算法的速度 1.冒泡排序

for(i=0;i<20000;i++) a[i]=rand(); s=clock();

for(i=0;ia[j]) { t=a[i]; a[i]=a[j]; a[j]=t; }

b=clock(); 运行时间：1407ms 2.选择排序

for(i=0;i<20000;i++) a[i]=rand(); s=clock();

for(i=0;i

for(j=0;ja[max])

max=j; b[i]=a[max];

a[max]=-1000000; }

t=clock();

运行时间：1220ms 3.插入排序

for(i=0;i<20000;i++) a[i]=rand(); s=clock(); for(i=0;i

for(j=i-1;j>=0;j--) if(a[j]>t) break;

for(l=i;l>j+1;l--) a[l]=a[l-1]; a[j+1]=t; }

t=clock(); 运行时间：984ms

以上三种都是O(n^2)的排序，其中插入排序最快，且可以用指针加以优化。从编程复杂度上，冒泡排序最简单。从算法的稳定性上，插入排序是稳定的，即排序后关键字相同的记录顺序不改变，特别适用于表达式处理等问题。一般的选择排序是不稳定的，但这里给出的程序由于使用了人类最原始的方法，即依次选择最大的并排除，故是稳定的。冒泡排序是不稳定的，涉及必须保持数据原顺序的题目时不能选择冒泡排序，而必须选择稳定的排序方式。

以下试验所采用的环境是： CPU Intel Core 1.73GHz*2，内存512M，操作系统Windows 7 Ultimate Beta，程序语言C。编译环境Dev-c++，以下称为2号机。由于CPU速度较慢，且操作系统占用资源较多，程序运行速度明显减慢，第一章的“基本运行测试”需要时间约为前者的2倍，即为406ms。故第一章的程序运行时间此处应乘2。

4.快速排序的标准版 #define MAX 10000000 int a[MAX]; int p(int l,int r)

{ int x=a[l],i=l-1,j=r+1,t; while(1) { do{--j;

}while(a[j]

}while(a[i]>x); if(i

{ t=a[i];a[i]=a[j];a[j]=t; }

在图论中，最短路算法是常见的。对于常见的几种算法，到底哪种更优，还是各有千秋？我们不妨一试。以下实验在1号机上进行，均为试验20次随机数取平均值的结果。

1.单源最短路径——dijkstra算法 void dijkstra() { int i,j,min=0; for(i=0;i

for(j=0;j

if(!use[j]&&d[i][j]

if(dis[min]+d[min][j]

随机数产生器： for(i=0;i

for(j=0;j

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

当MAX=2000时（即点数为2000个），运行时间：28.2ms。当MAX更大时，内存会使用过多，故在1s时限内至多运行规模为2000的单源最短路径35次。

2.单源最短路径——Ford算法 int ford() { int i,j;

for(i=1;i

if(d[f[j]]+w[j]

①数据构造：10*n条随机边。当n=1000时，运行时间：49.95ms。当n=10000时，运行时间：6766ms。②数据构造：n*n条边的完全图。当n=1000时，运行时间6469ms。比Dijkstra和SPFA都慢很多，因为其算法的理论时间复杂度就达到了O(VE)，属于介于O(n^2)与O(n^3)的算法。但我们仍然需要这种算法，因为当图中存在负权时，必须使用Ford算法。同时，该算法还能判断图中是否存在负权回路（无解）。

3.单源最短路径——SPFA算法 struct mising{ int num; int poo;

struct mising *p; };

int wor[500000]; int dis[60001];

int yes[60001]={0}; int beg=0,end=1; main() {

int n,m; int a,b,c,i;

struct mising q[60001],*qq[60001],*x; double s,t; FILE *fp;

fp=fopen(\

fscanf(fp,\ for(i=0;i

fscanf(fp,\ a--; b--;

qq[a]->p=(struct mising *)malloc(sizeof(struct mising)); qq[b]->p=(struct mising *)malloc(sizeof(struct mising)); qq[a]=qq[a]->p; qq[b]=qq[b]->p; qq[a]->poo=b; qq[b]->poo=a;

qq[a]->num=qq[b]->num=c; }

s=clock();

for(i=0;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[x->poo]==-1||(dis[x->poo]>x->num+dis[wor[beg]]&&dis[x->poo]!=-1)) {

dis[x->poo]=dis[wor[beg]]+x->num; wor[end]=x->poo; if(yes[x->poo]==0) {

yes[x->poo]=1; end++; } }

x=x->p; }

yes[wor[beg]]=0; beg++; }

printf(\ t=clock(); 随机数生成模块：

fprintf(fp,\ 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,\ }

运行时间（不含文件操作）：当n=100000时，运行时间1937ms；当n=10000时，运行时间141ms；当n=1000时，运行时间小于10ms。特别需要注意的是，当n=50000时，用时828ms，再加上文件操作用时，可称为是SPFA算法数据规模的上限。这组数据是n个点，10*n条随机边的情况下作出的。若使用O(n^2)的Dijkstra算法，时间将大幅增加。

对于单源最短路径，要考虑题意要求，稀疏图使用SPFA，密集图使用Dijkstra，以提高运行效率。

3.点对点最短路径——Floyed算法 void floyed() { int i,j,k,min=0; for(k=0;k

if(d[i][k]+d[k][j]

当MAX=500时，运行时间：979.85ms。这提示我们，点对点最短路径的规模最大为500，否则会超时。

若使用MAX-1次dijkstra算法 void dijkstra() { int i,j,k,min=0;

for(k=0;k

for(j=0;j

if(!use[j]&&d[i][j]

if(dis[min]+d[min][j]

当MAX=500时，运行时间：1625ms，与floyed的980ms相比，显然慢了很多。因此，floyed算法是点对点最短路径的“正统”算法。

三、字符串匹配算法的比较 1.朴素匹配算法 for(i=0;i<1000;i++) S[i]=1;

for(j=0;j<100000;j++) T[j]=1; s=clock(); tot=0;

ls=strlen(S); lt=strlen(T);

for(i=0;i

printf(\ 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&&T[q+1]!=S[i]) q=next[q];

if(T[q+1]==S[i]) q++; if(q==lt)

a[tot++]=i-lt+1; } }

void ff() { int q,k;

for(q=1;q<=lt;q++) {

k=next[q];

while(k>0&&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(k>0&&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时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++;

}

主程序： 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;imax) max=f[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++)

本文来源：https://www.bwwdw.com/article/akcg.html