文档介绍：算法效率与程序优化在信息学竞赛中,常遇到程序运行超时的情况。然而,同一个程序设计思想,用不同算法,会有不同的运行效率;而即使是同样的算法,由于在代码的细节方面设计有所不同,执行起来效率也会有所不同。当遇到所需时间较长的问题时, 一个常数级优化可能是 AC的关键所在。下面,我们就从代码细节与算法设计两方面, 比较不同程序执行时间的异同,从而选择其中较优的算法,提高程序运行效率。本试验所采用的环境是: ,内存248M,操作系统WindowsXPSP2,程序语言C。编译环境Dev-c++。以下称为1号机。。第一章各种运算的速度一、基本运算的速度为了增强算法效率的计算准确性,我们采用重复试验 20次取平均值的做法。每次试验运行100000000次。基本运行时间,是指在准备计算的运算复杂度之外,只包括循环控制变量的加减与比较所消耗的时间。要从实际运行时间中减去基本运行时间,才是这种运算真正的运行时间,称为净运行时间。#include<>main(){inti,j;doublea,b,sum=0;for(j=0;j<20;j++){//此处添加随机数产生a=clock();for(i=0;i<100000000;i++);//此处添加运算b=clock();printf("%lf\n",b-a);sum+=b-a;}printf("ans=%lf',sum/);Igetch();}运行平均时间是:。(1),与基本运行时间 ,可忽略不计,故以后将赋值运算作为基本运行时间的一部分,不予考虑。(2)加法运算产生随机数:x=rand();y=rand();循环内加法:t=x+y;下面的各种简单运算只是更改运算符即可,不再写出代码。,即:在1s的时限中,共可进行(1000-)/*10人8=*10人9次加法运算,即:只通过循环、加法和赋值的运算次数不超过 *10A9.。而应用+=运算,与普通加法时间几乎相同,所以 +=只是一种方便书写的方法,没有实质效果。同样的,各种自运算并不能提高效率。(3),与加法运算基本相同。可见,在计算机内部实现中,把减法变成加法的求补码过程是较快的, 而按位相加的过程占据了较多的时间, 借用化学中的一句术语,可以称为整个运算的“速控步”。当然,这个“速控步”的运行速度受计算机本身制约,我们无法优化。在下面的算法设计中,还会遇到整个算法的“速控步” ,针对这类情况,我们要对占用时间最多的步骤进行细心优化,减少常数级运算次数。(4) ,明显比加减法要慢,但不像某些人想象的那样慢,至少速度大于加减法的1/2。所以在实际编程时,没有必要把两个或三个加法变成乘法,其实不如元素乘常数来得快。不必“谈乘色变”,实际乘法作为CPU的一种基本运算,速度还是很快的。以上四种运算速度都很快,比循环所需时间少很多,在普通的算法中,每个最内层循环约含有4-5个加、减、乘运算,故整个算法的运行时间约为循环本身所需时间的 2倍。(5) ,是四种常规运算中最慢的一种,耗时是加法的 28倍,,确实如常人所说“慢几十倍”,一秒的时限内只能运行 *10A7次,不足一亿次,远大于循环时间。所以,在计算时应尽量避免除法,尤其是在对时间要求较高的内层循环,尽量不安排除法,如果整个循环中值不变, 可以使用在循环外预处理并用一个变量记录, 循环内再调用该变量的方法,可以大大提高程序运行效率。(6) ,与除法运算速度几乎相当,都非常慢。所以,取模运算也要尽量减少。在大数运算而只要求求得MODN的值的题目中,应尽量利用数据类型的最大允许范围,在保证不超过MAXINT的前提下,尽量少执行 MOD运算。例如在循环数组、循环队列的应用中,取模运算必不可少,这时优化运算便十分重要。可利用计数足够一定次数后再统一MOD,循环完后再MOD,使用中间变量记录MOD结果等方法减少次数。在高精度计算中,许多人喜欢边运算边整理移位,从而在内层循环中有除、模运算各一次,效率极低。应该利用 int的数据范围,先将计算结果保存至当前位,在各位的运算结束后再统一整理。以下是用统一整理法编写的高精度乘法函数,规模为 10000位。inta[10000]={0},b[10000]={0},c[10000]={0};voidmul(){inti,j,t;for(i=0;i<10000;i++)for(j=0;j<10000-i;j++)