倍增思想的研究.doc

倍增思想的研究 安徽省芜湖市第一中学 朱晨光 前言 倍增思想是信息学中一种非常重要的思想，近几年中越来越受到人们的重视，应用也日趋广泛。倍增思想的本质并不复杂，但是要想在特定的题目中恰当地运用好倍增思想却并不容易。因此，本文将从两个方面的运用来探讨倍增思想，并在其中总结倍增思想的实质与理论基础。 关键字 倍增思想 正文 倍增思想是一种十分巧妙的思想。“倍增”二字体现在它每次将当前的已知结果或考察范围扩大一倍。正是由于这个原因，它的时间复杂度降低了很多，一般是将一个系数N变为log2N。举一个简单的例子，如果我们想把1变成16，可以每次加1，这样需要操作15次；还可以每次将当前的数乘以2，这样只需要操作4次。这还只是针对16这个比较小的数。如果是32768(215)，1048576(220)，2147483648(231)，……，那么节省的操作次数就非常多了。因此，在这里，我们先对倍增思想有一个感性的认识——即每次通过“翻番”来减少操作次数。 倍增思想的运用是十分广泛的。一般来说，有如下两种情况： 一、 将一个状态经过若干次变化得到另一个状态，而每次变化的规则都是相同的。这时，可以借助倍增思想，每次将考察的两个状态之间的距离增大一倍，从而减小时间复杂度； 二、 每次需要对一段区间进行某种操作（一般是统计操作）。这时可以利用倍增思想，在预处理中得到这段区间中的每一点向后长度为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+……+2bw.其中，b1b2……bw=0.很明显，这一步操作可以通过将n表示成为一个二进制数实现，若第x位为1，则x必等于某个bi.为了后面处理方便，这里建立一个集合B={b1,b2,……,bw}. 第二步：根据幂运算的有关规则，==**……*.这为第三步指明了方向：即高效地求出，，……，。 第三步：由于已知a,即，因此可以每次将当前结果进行平方，即由得到*，即.另设一个result,初值为1。如果当前结果为且iB, 则令result←result*.这样，在取遍了B集合中每一个值后，result便为最终结果. 那么，这样的操作需要进行多少次呢？根据二进制数的性质，十进制数n的二进制表示一定不超过位。也就是说，其中最多有个1且最高位是第位. 因此，最多进行次平方操作就可以得到所有需要的值。而对于每个还要与result进行一次乘法操作，所以总的乘法操作次数最多为2，是O(log2n)级别的。其中省去的乘法操作很好理解：举一个例子，在从得到的过程中，按照原始的方法需要进行2i次乘法操作，而现在只需要利用已知结果进行一次乘法操作即可。大大减少了操作次数，从而降低了时间复杂度。 实际运用中，这个a并不仅仅可以表示一个实数，还可以是一个矩阵或是一个抽象意义上的状态。从这个归纳中，可以看出，倍增思想在这种情况下的运用具有如下性质： 求从一个状态经过n次相同规则的变化得到的另一个状态； 这种规则下的变化具有结合率。 在这种情况下，只需要将n表示成为一些互不相等的2的幂的和，然后利用幂运算的有关性质，将求转化为求一些a的2的乘方的幂的乘积。而从a即开始，每次进行平方操作，即可在O(log2n)时间内得到问题的解。 下面举一些例题进行说明： 有一个N*N的矩阵A，求矩阵AK（即K个A连乘后的结果），其中每一个数都为对10000取模后的值。注意：矩阵乘法具有结合率。 分析： 经过对上面那个小例子的深入探究，这题就变得十分简单了。只要将例子中实数a变为矩阵A即可。时间复杂度为O(N3*log2K)，空间复杂度为O(N2). 骰子的运动 给定一个六个面的骰子，每个面上都有一定的权值（1到50之间的整数）。骰子运动的范围是一个宽度为4，向左右无限延伸的带子。带子从左到右的横坐标值为……，-3，-2，-1，0，1，2，3，……，从前到后的纵坐标值依次为1，2，3，4（这里的坐标对应的都是格子，而不是点）。这样，带子被分成了无限多个格