算法合集之《减少冗余与算法优化》

《算法合集之《减少冗余与算法优化》》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、IOI2004国家集训队论文胡伟栋减少冗余与算法优化长沙市长郡中学胡伟栋【摘要】在信息学竞赛中，我们经常会遇到冗余，而冗余会造成算法、程序的效率不同程度的降低：有的是微不足道的，而有的会导致算法复杂度大大提高。本文针对后者，举例说明冗余对算法效率的影响和如何减少冗余。【关键字】冗余、算法优化【正文】一引言信息学竞赛中，我们所追求的目标之一，是使程序用最少的时间解决问题，也就是达到最高的效率。实际生活中也同样需要这样，高效率者往往会在竞争中取得优势。冗余，是指多余的或重复的操作。在搜索、递推、动态规划等诸多的算法中，都会

2、出现冗余。由冗余的定义，要使算法达到最高的效率，必须去除算法中的冗余处理。但完全去除冗余是难以实现的，使程序用绝对最少的时间解决问题也是很难的，通常需要退一步，将目标改为：使程序用尽量少的时间解决问题。由冗余的定义，可以得到：要提高算法的效率，必须减少算法中的冗余处理。要减少冗余，需要在大量的做题过程中，不断探索，不断积累经验。下面就让我们通过两个具体的例子来研究冗余是如何影响算法效率的以及如何减少冗余。二整数拆分①2.1问题描述将正整数N拆分成若干个整数的和，使拆分成的数是2的非负整数幂的形式。问有多少种拆分方案。如

3、果两个方案仅有数的顺序不同，它们算作同一种方案。如：当N=5时，可以拆分成下面的形式：5=1+1+1+1+15=1+1+1+25=1+2+25=1+4①题目来源：金恺原创第1页共10页IOI2004国家集训队论文胡伟栋所以，5有4种拆分方案。2.2粗略分析此题可用递推解决(为什么？请读者自己思考^_^)：j用F[ij,]表示i拆分成若干个数，其中最大的数不超过2的拆分总数。则：1°Fj[0,]1=02°Fi[,0]1=，即i拆分成若干个数，其中最大的数不超过21=的拆分方案只有一种：把i拆分成i个1。3°当i>0,j>

4、0时，F[ij,]由两类组成：jj第一类：拆分成的最大数正好是2，其总数为F[ij-2,]；j第二类：拆分成的最大数小于2，其总数为F[ij,-1]。j所以F[i,j]=F[i-2,j]+-F[ij,1]。最后要计算的目标是F[N,M]。j因为i-2必须³0，所以ji£êúëûlog，又有1££iN。不难得出：总的时间2①复杂度是O(NNlog)，空间复杂度也是O(NNlog)。看上去，这个复杂度已22经很低了。但是，复杂度能不能再低一点儿呢？2.3减少冗余为了便于研究，可以首先处理N是2的整数幂这种特殊情况，然后把N

5、不是2的整数幂的情况化为N是2的整数幂的情况处理。2.3.1当N是2的整数次幂时M设N=2(M为非负整数)。首先，为了讨论时更直观，把所有的F[ij,]对应到以I为横轴，J为纵轴的直角坐标系中的每一个整点上，将横坐标为i的点称为第i列的点、纵坐标为j的点称为第j行的点。(F[ij,]是第i列，第j行的点)②若点C是点A与点B的和，则连有向边AC和BC(如图A所示)。①此处所讲的时空复杂度都忽略了高精度的因素。因为当N达到10000000时答案也只有60位，这个数字是比较小的。②j当C为F[ij,]时，由

6、递推方程，A、B分别为F[ij-2,]、F[ij,-1]。第2页共10页IOI2004国家集训队论文胡伟栋J3jA(F[ij-2,])C(F[ij,])21B(F[ij,-1])012345678I图A(M=3，N=8)根据递推关系将所有的边都连出来，可以得到图B。JD32E1012345678I图B(M=3，N=8)M观察要计算的目标F[NM,]，它是F[N-=2,M]FM[0,]与F[NM,-1]的M-1和，而F[NM,-1]是F[NM--2,1]与F[NM,-2]的和；F[NM,-2]是M-2F[NM--2,2]

7、与F[NM,-3]的和……可以看出，图中有很多的点(如图B中的D，E)的值求出与不求出都不影响最后的答案，所以这些点都没必要求出，都是冗余的，在图中也没必要向这些点连边。将这些冗余的点和边删掉，只留下最后可能影响到目标点的点和边，图B变成了图C的样子，可以看出，图C比图B简洁多了，要计算的点数也少多了。J321012345678I图C(M=3，N=8)那么，到底要计算多少个点呢？观察图C，发现当j达到最大，即jM=时第j行只需要计算1个值——NF[NM,]；当jM=-1时第j行要计算2个值——F[NM,-1]和FM[,

8、-1]；当2第3页共10页IOI2004国家集训队论文胡伟栋NN3NjM=-2时第J行要计算4个值——FM[,-2]、FM[,-2]、FM[,-2]424和F[NM,-2]……由此可以猜想：k①当j=-Mk时第j行要且只要计算2个值。jkk②这些要计算的值是Fj[ll2,](1££2)这2个。这两个猜想是否正确呢？答案是肯定的，下