文档介绍：倍增思想的研究
安徽省芜湖市第一中学朱晨光
前言
倍增思想是信息学中一种非常重要的思想,近几年中越来越受到人们的重视,应用也日趋广泛。倍增思想的本质并不复杂,但是要想在特定的题目中恰当地运用好倍增思想却并不容易。因此,本文将从两个方面的运用来探讨倍增思想,并在其中总结倍增思想的实质与理论基础。
关键字
倍增思想
正文
倍增思想是一种十分巧妙的思想。“倍增”二字体现在它每次将当前的已知结果或考察范围扩大一倍。正是由于这个原因,它的时间复杂度降低了很多,一般是将一个系数N变为log2N。举一个简单的例子,如果我们想把1变成16,可以每次加1,这样需要操作15次;还可以每次将当前的数乘以2,这样只需要操作4次。这还只是针对16这个比较小的数。如果是32768(215),1048576(220),2147483648(231),……,那么节省的操作次数就非常多了。因此,在这里,我们先对倍增思想有一个感性的认识——即每次通过“翻番”来减少操作次数。
倍增思想的运用是十分广泛的。一般来说,有如下两种情况:
一、将一个状态经过若干次变化得到另一个状态,而每次变化的规则都是相同的。这时,可以借助倍增思想,每次将考察的两个状态之间的距离若A状态需要经过x次变化得到B状态,则称A与B的距离是x.
增大一倍,从而减小时间复杂度;
二、每次需要对一段区间进行某种操作(一般是统计操作)。这时可以利用倍增思想,在预处理中得到这段区间中的每一点向后长度为20,21,22,……(包括自己)的子区间的某种性质,以便在处理中O(1)或O((log2N)x)地取用。
下面,将就上面每种情况进行分析,并举出例题具体说明。
情况一变化规则相同的情况下用倍增思想加速状态转移
首先举一个小例子:在求320时,可以用3*3*3*……*3实现,共要做19次乘法。还可以将320分解为316*34,并且可以由3经一次乘法得到32,32经一次乘法得到34,34经一次乘法得到38,38经一次乘法得到316。因此,只需要4次乘法就可以得到所需要的316与34,再进行一次乘法就得到了320,总共只需要5次乘法。
那么,在这里倍增思想究竟是如何减少了运算次数呢?让我们先将这种方法做一个归纳:
在求时,如果a的乘法运算满足结合率,那么就可以任意地决定这(n-1)次乘法操作的顺序。而倍增思想是这样做的:
第一步:将n表示成为2b1+2b2+……+,b1>b2>……>bw>=,这一步操作可以通过将n表示成为一个二进制数实现,若第x位为1,,这里建立一个集合B={b1,b2,……,bw}.
第二步:根据幂运算的有关规则,==**……*.这为第三步指明了方向:即高效地求出,,……,。
第三步:由于已知a,即,因此可以每次将当前结果进行平方,即由得到*,,初值为1。如果当前结果为且iB, 则令result←result*.这样,在取遍了B集合中每一个值后,result便为最终结果.
那么,这样的操作需要进行多少次呢?根据二进制数的性质,十进制数n的二进制表示一定不超过位。也就是说,其中最多有个1且最高位是第位. 因此,最多进行次平方操作就可以得到所有需要的值。而对于每个还要与result进行一次乘法操作,