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

IOI2004国家集训队论文胡伟栋

减少冗余与算法优化
长沙市长郡中学胡伟栋

【摘要】
在信息学竞赛中，我们经常会遇到冗余，而冗余会造成算法、程序的效率不
同程度的降低：有的是微不足道的，而有的会导致算法复杂度大大提高。本文
针对后者，举例说明冗余对算法效率的影响和如何减少冗余。

【关键字】
冗余、算法优化

【正文】

一引言
信息学竞赛中，我们所追求的目标之一，是使程序用最少的时间解决问题，
也就是达到最高的效率。实际生活中也同样需要这样，高效率者往往会在竞争中
取得优势。
冗余，是指多余的或重复的操作。在搜索、递推、动态规划等诸多的算法中，
都会出现冗余。
由冗余的定义，要使算法达到最高的效率，必须去除算法中的冗余处理。但
完全去除冗余是难以实现的，使程序用绝对最少的时间解决问题也是很难的，通
常需要退一步，将目标改为：使程序用尽量少的时间解决问题。由冗余的定义，
可以得到：要提高算法的效率，必须减少算法中的冗余处理。
要减少冗余，需要在大量的做题过程中，不断探索，不断积累经验。
下面就让我们通过两个具体的例子来研究冗余是如何影响算法效率的以及
如何减少冗余。

二整数拆分

2.1问题描述①
将正整数N拆分成若干个整数的和，使拆分成的数是2的非负整数幂的形
式。问有多少种拆分方案。如果两个方案仅有数的顺序不同，它们算作同一种方
案。
如：
当N=5时，可以拆分成下面的形式：
5=1+1+1+1+1
5=1+1+1+2
5=1+2+2
5=1+4

①题目来源：金恺原创

IOI2004国家集训队论文胡伟栋

所以，5有4种拆分方案。

2.2粗略分析
此题可用递推解决(为什么？请读者自己思考^_^)：
用F[ij,]表示i拆分成若干个数，其中最大的数不超过2j的拆分总数。则：

1°Fj[0,]1=

2°Fi[,0]1=，即i拆分成若干个数，其中最大的数不超过210=的拆分方案
只有一种：把i拆分成i个1。
3°当i>0,j>0时，F[ij,]由两类组成：

第一类：拆分成的最大数正好是2j，其总数为F[ij-2j,]；

第二类：拆分成的最大数小于2j，其总数为F[ij,-1]。

所以F[i,j]=F[i-2j,j]+-F[ij,1]。
最后要计算的目标是F[N,M]。
因为j必须，所以，又有。不难得出：总的时间
i-2³0ji£ëûêúlog21££iN

①
复杂度是O(NNlog)2，空间复杂度也是O(NNlog)2。看上去，这个复杂度已
经很低了。但是，复杂度能不能再低一点儿呢？

2.3减少冗余
为了便于研究，可以首先处理N是2的整数幂这种特殊情况，然后把N不
是2的整数幂的情况化为N是2的整数幂的情况处理。

2.3.1当N是2的整数次幂时

设N=2M(M为非负整数)。首先，为了讨论时更直观，把所有的F[ij,]对应
到以I为横轴，J为纵轴的直角坐标系中的每一个整点上，将横坐标为i的点称
为第i列的点、纵坐标为j的点称为第j行的点。(F[ij,]是第i列，第j行的点)

若点C是点A与点B的和②，则连有向边AC和BC(如图A所示)。

①此处所讲的时空复杂度都忽略了高精度的因素。因为当N达到10000000时答案也只有60位，这个数字
是比较小的。
②当C为F[ij,]时，由递推方程，A、B分别为F[ij-2j,]、F[ij,-1]。

IOI2004国家集训队论文胡伟栋

J
3
j
A(F[ij-2,])C(F[ij,])
2

1
B(F[ij,-1])
012345678I
图A(M=3，N=8)
根据递推关系将所有的边都连出来，可以得到图B。
J
D
3

2E

1

012345678I
图B(M=3，N=8)
观察要计算的目标F[NM,]，它是F[N-=2M,M]FM[0,]与F[NM,-1]的

和，而F[NM,-1]是F[NM--2M-1,1]与F[NM,-2]的和；F[NM,-2]是

F[NM--2M-2,2]与F[NM,-3]的和……可以看出，图中有很多的点(如图B中
的D，E)的值求出与不求出都不影响最后的答案，所以这些点都没必要求出，都
是冗余的，在图中也没必要向这些点连边。将这些冗余的点和边删掉，只留下最
后可能影响到目标点的点和边，图B变成了图C的样子，可以看出，图C比图
B简洁多了，要计算的点数也少多了。

J
3

2

1

012345678I
图C(M=3，N=8)

那么，到底要计算多少个点呢？
观察图C，发现当j达到最大，即jM=时第j行只需要计算1个值——
N
F[NM,]；当jM=-1时第j行要计算2个值——F[NM,-1]和FM[,-1]；当
2

IOI2004国