国家集训队2000论文集 张一飞论文(2)

冗繁削尽留清瘦——浅谈信息的充分利用 张一飞

图3初步利用信息，优化算法2-1

为了表示出图3的思想，

设MaxFV[i]?maxMaxFV[i]?max(0?j?k?i)(0?j?k?i){F[j]/V[k]}，则{F[j]/V[k]}{F[j]/V[k]},max(0?j?i?1)(0?j?k,k?i?1)?max{max(0?j?k?i?1){F[j]/V[k]}}?max{MaxFV[i?1],max?max由公式2，F[i]?max?max(0?j?i){F[j]/V[i?1]}}{MaxFV[i?1],F[j]/V[i?1]}{F[j]/V[k]*V[i]}{F[j]/V[k]}*V[i]

(0?j?k?i)(0?j?k?i)?MaxFV[i]*V[i]这样，我们得到如下递推关系式：

公式5：F[i]?MaxFV[i]*V[i]MaxFV[i]?max(0?j?i)

{MaxFV[i?1],F[j]/V[i?1]}从公式5中可以看出，在确定MaxFV[i]时，较充分的利用了确定MaxFV[i-1]时产生的结果。采用公式5可得算法2-2，它的时间复杂度为O(M2)，空间复杂度是O(M)。

算法2-2

F[0]:=1;MaxFV[0]:=0;V[0]:=1; for i:=1 to M do begin

MaxFV[i]:=MaxFV[i-1]; for j:=0 to i-1 do

MaxFV[i]:=Max{MaxFV[i],F[j]/V[i-1]} F[i]:=MaxFV[i]*V[i] end;

将公式5化简，有

MaxFV[i]?max?max(0?j?i){MaxFV[i?1],F[j]/V[i?1]}{MaxFV[i?1],MaxFV[j]*V[j]/V[i?1]}(0?j?i)

在这个公式中，MaxFV[i]可以看作是前i-1天所能获得的最多股票数。这种

状态表示方法和公式3中P[i]的含义本质上是相同的。这样，我们通过对已知信息的利用，达到了改变动态规划中状态表示含义的效果。

第 6 页

冗繁削尽留清瘦——浅谈信息的充分利用 张一飞

<4>.充分利用信息，进一步优化算法2-2

在算法2-2中，进一步利用信息，很容易得到时间复杂度为O(M)的算法。 算法2-2的粗体部分的功能是确定MaxFV[i]所能达到的最大值。由于V[i-1]不变，因此F[j]/V[i-1]达到最大值，当且仅当F[j]达到最大值，其中0≤j

算法2-2中内层循环实质上是在确定MaxFV[i]时，找到F[0],F[1],…F[i-1]中的最大值。而在确定MaxFV[i-1]时，我们已经找到了F[0],F[1],…,F[i-2]中的最大值。如果把这个信息利用起来，就可以更快的确定F[0],F[1],…F[i-1]中的最大值。

设MaxF[i]?maxMaxF[i]?max(0?j?i)(0?j?i){F[j]}，则{F[j]}(0?j?i?1)?max{max{F[j]},F[i?1]}

?max{MaxF[i?1],F[i?1]}MaxFV[i]?max(0?j?i){MaxFV[i?1],F[j]/V[i?1]}?max{MaxFV[i?1],MaxF[i]/V[i?1]}这样，我们得到如下递推关系式：

公式6：F[i]?MaxFV[i]*V[i]MaxFV[i]?max{MaxFV[i?1],MaxF[i]/V[i?1]}MaxF[i]?max{MaxF[i?1],F[i?1]}

从公式6中可以看出，在确定MaxF[i]时，充分利用了确定MaxF[i-1]时所产生的信息。采用公式6可得算法2-3，它的时间复杂度是O(M)。从公式6中的三个递推关系式可以看出，当前状态都只与前一个状态有关，因此，空间复杂度可以进一步降到O(1)[6]。

算法2-3

F:=1;MaxF:=0;MaxFV:=0;V[0]:=1; for i:=1 to M do begin

if F>MaxF then MaxF:=F;

if MaxF/V[i-1]>MaxFV then MaxFV:=MaxF/V[i-1]; F:=MaxFV*V[i] end;

公式6中MaxF[i]可以看作是前i-1天能达到的最大收入[7]。虽然这种状态表示方法和公式4中Q[i]是类似的，但算法的时间复杂度却从O(M2)降到了O(M)，空间复杂度也从O(M)降到了O(1)。这样，我们通过充分利用已知信息，达到了改变状态表示难以达到的优化效果。

<5>.小结

下面是三个算法的性能分析表： 分析项目 算法2-1 算法2-2 算法2-3 O(M3) O(M2) O(M) 理论时间复杂度 O(M) O(M) O(1) 分析 空间复杂度 4s 0.05s <0.05s 实际M=200的随机数据 >60s 1s <0.05s 运行M=1000的随机数据 >60s 5s <0.05s 情况 M=2000的随机数据 第 7 页

冗繁削尽留清瘦——浅谈信息的充分利用 张一飞

在这道题中，我们通过避免冗余运算，将时间复杂度由O(M3)先降到O(M2)，再进一步降到O(M)。空间复杂度也从O(M)降到了O(1)。

由此可见，充分利用信息，提高动态规划的效率，是非常有效的。此外，充分利用信息并不一定要以牺牲空间为代价，同样可以优化算法的空间复杂度。

三、 提高数值计算的效率

从前面的分析中，我们深深地体会到了动态规划的核心思想——充分利用已知信息。但这个思想并不仅限于动态规划。下面我们将看到，充分利用已知信息，对提高数值计算的效率，也十分有效。

我们看一道数值计算题：

【高精度计算问题】(湖南1998省赛试题)

输入n,m,k，计算Sm(n)的后k位数。其中Sm(n)=1m+2m+…+nm，1≤k≤99，1≤n,m≤9999。

<1>.分析

由于k可以达到99，因此必须采用高精度计算。本题只要求出Sm(n)的后k位数，所以，每次计算只取结果的后k位数即可。显然，计算Sm(n)将耗费大量的时间用于乘幂运算。下面，我们分析乘幂运算的算法。

<2>.朴素的乘幂算法

根据乘幂的定义，我们将i自乘m次即可。 算法3-1，计算im Func Power(i,m); begin

SetValue(x,1); {x是高精度数} for k:=1 to m do

x:=Mul(x,i); {Mul是高精度乘法，返回x*y的值} Power:=x end;

采用算法3-1计算im，需要进行M次高精度乘法。

<3>.粗略利用信息，优化算法3-1

算法3-1对信息的利用很不充分。例如，要计算i5，现在已经求出了i3的值，算法3-1会利用i3和i的值，求出i4，进而求出i5。而实际上，在计算i3之前，我们已经求出了i2的值，将i3乘上i2，就可以求出i5。

我们用数组p[k]保存已经计算出的ik的结果，在计算过程中，尽可能的使用已经计算过的信息。例如，我们可以这样计算i15：

p[1]=i

p[2]=p[1]*p[1] p[3]=p[2]*p[1] p[6]=p[3]*p[3] p[7]=p[6]*p[1] p[14]=p[7]*p[7] p[15]=p[14]*p[1]

这样，我们只用了6次高精度乘法，就求出了i15。

第 8 页

冗繁削尽留清瘦——浅谈信息的充分利用 张一飞

从上面的例子可以看出，将一个已知结果平方，就可以只用一次乘法，求出一个比较大的指数幂，根据这个思想就可得到算法3-2：

im?m2?(i2) ??m?1?i(i2)2?m为偶数m为奇数

算法3-2，计算im

Func Power(i,m); begin

if m=1 then Power:=i else begin

Temp:=Power(i,m div 2); Temp:=Mul(Temp,Temp);

if Odd(m) then Power:=Mul(Temp,i) else Power:=Temp end end;

算法3-2计算im需要O(log2m)次高精度乘法。这样，我们通过对信息的粗略利用[8]，将时间复杂度从O(m)降到了O(log2m)。

算法3-2实质上就是二分法。采用二分法求乘幂，之所以比累乘的方法高效，就在于它更加充分的利用了已知信息。

<4>.充分利用信息，进一步优化算法3-2

注意到在计算im时，我们已经知道了1m,2m,…,(i-1)m的值，而这些值在算法3-2计算im时没有起任何作用。如果能够建立im与1m,2m,…,(i-1)m的关系，就可更快计算im。

例如，求120m。这时，我们已经计算了5m和24m的值。显然，5m和24m相乘，就可以得到120m。

当i是合数时，设i=pq，其中1

采用这种方法得到算法记为算法3-3。设1..n中，有x个合数，则算法3-3只做了(n-x)log2m+x次高精度乘法。自然数中素数的分布十分稀疏，实践证明，当n=m=9999,k=99时，算法3-3的效率是算法3-2的5倍。

<5>.小结

下面是三个算法的性能分析表： 分析项目 算法3-1 算法3-2 算法3-3 O(nm) O(nlog2m) O(nlog2m) 理论时间复杂度 O(k) O(k) O(nk) 分析 空间复杂度 N=M=100,K=99 0.1 <0.05 <0.05 实际N=100,M=9999,K=99 20s 0.5s 0.1s 运行N=M=1000,K=99 15s 3s 1s 情况 N=M=9999,K=99 >60s 55s 10s 在这个例子中，我们首先通过对信息的粗略利用，优化朴素的乘幂算法3-1，

第 9 页

冗繁削尽留清瘦——浅谈信息的充分利用 张一飞

得到采用二分法的算法3-2。进一步分析发现，二分法在计算im时，没有利用已经求出的1m,2m,…,(i-1)m等信息，充分利用这些信息，得到了更快的算法3-3。由于算法3-3需要保存一些已经求过的值[9]，所以，该算法实质上是以空间为代价换取了时间。

四、 结束语

在搜索中加入记忆化信息提高回溯法的效率，改变动态规划中状态表示的含义提高动态规划的效率，采用二分法提高数值计算的效率，都不同程度的体现了对已知信息的充分利用。但仅使用这些常用技巧优化算法，仍可能存在多余的运算。如果能够更加充分的利用已知信息，就可以收到更好的效果。

在算法中削去冗繁，关键在于找到可利用的已知信息，一旦把它们充分利用起来，就可以大大提高算法效率。

【参考文献】

1. 《信息学奥林匹克》. 1999(3)

2. 吴文虎，王健德 .《实用算法与程序设计》. 电子工业出版社 . 1998.01

3. 刘福生，王建德 .《青少年国际信息学（计算机）奥林匹克竞赛指导——人工智能搜索与程序设计》. 电子工业出版社 . 1993.04 4. 《郑板桥集》

第 10 页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库国家集训队2000论文集 张一飞论文(2)在线全文阅读。