资源描述：
《论文国家队胡伟栋》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、减少冗余与算法优化长沙市长郡中学胡伟栋1摘要】在信息学竞赛中，我们经常会遇到冗余，而冗余会造成算法、程序的效率不同程度的降低：有的是微不足道的，而有的会导致算法复杂度大大提高。本文针对后者，举例说明冗余对算法效率的影响和如何减少冗余。【关键字】冗余、算法优化1正文】引言信息学竞赛屮，我们所追求的口标之一，是使程序用最少的时间解决问题,也就是达到最高的效率。实际生活中也同样需要这样，高效率者往往会在竞争中収得优势。冗余，是指多余的或重复的操作。在搜索、递推、动态规划等诸多的算法中,都会出现兀余。曲冗余的定义，要使算法达到最高的效率，必须去除算法中的冗余处理。
2、但完全去除兀余是难以实现的，使程序用绝对最少的时间解决问题也是很难的，通由兀余的定义,常需要退一步，将忖标改为：使程序用尽量少的时间解决问题。可以得到：要提高算法的效率，必须减少算法中的冗余处理。要减少兀余，需要在大量的做题过程屮，不断探索，不断积累经验。下面就让我们通过两个具体的例子来研究冗余是如何彫响算法效率的以及如何减少兀余。二整数拆分2.1问题描述①将正整数N拆分成若干个整数的和，使拆分成的数是2的非负整数幕的形式。问有多少种拆分方案。如果两个方案仅有数的顺序不同，它们算作同一种方案。如：当N=5时，可以拆分成下面的形式：5=14-1+1+1+15
3、=1+14-1+25=1+2+25=1+4①题目來源：金恺原创第1页共10页所以，5有4种拆分方案。2.2粗略分析此题可用递推解决（为什么？请读者自己思考5用F[iJ]表示i拆分成若干个数，其中最大的数不超过2,的拆分总数。则:1°F[OJ]=12°FfZ,01=1,即I拆分成若干个数，其屮最大的数不超过2o=l的拆分方案只有一种：把i拆分成i个1o3°当z>0j>0时，F[i,j]由两类组成：第一类：拆分成的最大数止好是2）,其总数为F[i2第二类：拆分成的最人数小于2j,其总数为F[iJ1]。所以F[i9j]=F[i2)J]+F[jJl]o最后要计算的
4、
5、=[标是F[N,M]o因为i2/必须wO,所以Ilog2/
6、J,又有18/5/Vo不难得出：总的时间复杂度是0（N阻2N）①,空间复杂度也是O（NgN）o看上去，这个复杂度已经很低了。但是，复杂度能不能再低一点儿呢？2.3减少冗余为了便于研究，可以首先处理W是2的整数幕这种特殊情况，然后把N不是2的整数幕的情况化为N是2的整数幕的情况处理。2・3・1当N是2的整数次幕时把所有的F[iJ]对应将横坐标为z的点称设N=2m（M为非负整数）。首先，为了讨论时更直观,到以I为横轴，丿为纵轴的直角坐标系中的每一个整点上,为第i列的点、纵坐标为j的点称为第/行的点
7、。是第i列，第丿•行的点）若点C是点A与点B的和②，则连有向边AC和BC（如图A所示）。①此处所讲的时空复杂度都忽略了高粹度的因索。因为当N达到10000000时答案也只有60位，这个数字是比较小的。©当C为F[iJ]时，由递推方程，A、B分别为F[i2丿J]、F[iJ1]。第2页共10页J32C(F[iJ])11])0123456图A(M=3,N=078I根据递推关系将所有的边都连出来，可以得到图BoJD321E0123456图B(M=3,/V=8)78I观察耍计算的冃标F[N,M],它是F[N2.w,M]=F[0,M]与F[N,M1]的和，而F[N1]
8、是2mi,M1]与F[N,M2]的和；F[N,M2]是F[N2a/2,M2]与F[N3]的和……可以看出，图中有很多的点(如图B中的D,E)的值求出与不求出都不影响最后的答案，所以这些点都没必要求出，都是冗余的，在图中也没必要向这些点连边。将这些兀余的点和边删掉，只留下最后可能影响到冃标点的点和边，图B变成了图C的样子，可以看岀，图C比图B简洁多了，要计算的点数也少多了。3210123456781图C(M=3,N=8)那么，到底要计算多少个点呢？观察图C,发现当j达到最大，即j=M时第丿•行只需要计算1个值F[N,M]；当j=M1时第j行要计算2个值——F
9、N,M1]和F[1]j=M2时第J行要计算4个值——F[-,M2]、F[-2]、F[-,M2]Ii4和F[N9M2J……由此可以猜想：①当j=M氐时第丿行要且只要计算2,个值。k这两个猜想是否正确呢？答案是肯定的，下面用归纳法证明：1°当j=M时，第丿行只要计算F[N,M],这是显然的。猜想①、②此时都成立。k1个数。取j'=j=Mk,当/=/o时，由于第J行耍计算F[/o2./,j],由递推方程，第广行要计算F仏2八广]=F[2*/°2八广]，而计算川2*厶2・，广]乂要用到F[(2/o1)*2厂,广],计算F[(2/o1)*2•厂，广]时要用至IJ
10、F[(2/o2)*2；,/]……，-直下去,最后所有的F[x*2>
