下载掌阅APP，畅读海量书库
立即打开
从上一节中我们了解到指数爆炸在密码学中的应用。这里利用了增加密钥长度的方法使得暴力破译的复杂度（即尝试译码的次数）爆炸式地增长，从而提高了整个加密系统的安全性。但是细心的读者可能会发现，之所以暴力破译的复杂度会随着密钥长度 n 的增加而爆炸式的增长，是因为暴力破译法的时间复杂度为 O （2 n ），其中 n 为密钥Key的长度，也就是说最坏的尝试次数 c 与密钥的长度 n 之间存在着函数关系 c =2 n 。因为这里面底数常量为2（大于1），所以 c 会随着 n 的增加而急速膨胀。这个增长趋势可通过函数 y =2 x 的曲线（如图1-4所示）表现出来。
图1-4 函数 y =2 x 的曲线
我们很容易看出函数 y =2 x 中因变量 y 会随着自变量 x 的增加而加速增长，这就是所谓的指数爆炸现象。
如果我们逆向思维一下，当底数常量小于1而大于0时，即 c = q n ，0< q <1， c 会随着 n 的增加怎样变化呢？
我们通过下面这个实例理解这个问题。
电视台有一档竞猜商品价格的节目，主持人给出某一种商品的价格区间，竞猜者需要在规定的时间内猜出这个商品的实际价格。竞猜者每猜出一个价格时，主持人会根据竞猜者猜出的价格与该商品实际的价格的高低给出提示，要么是“价格猜高了”，要么是“价格猜低了”，或者是“猜的正确”。
已知商品的价格均为整数，不含角分，现在竞猜一个商品的价格，主持人给出价格区间为［1，1 000］元，而该商品的实际价格为625元，规定竞猜者必须在两分钟内猜出价格为获胜。请问这个竞猜者要怎样竞猜才能保证在两分钟内一定猜出该商品的价格。
要从1～1 000中找到正确的价格，最笨的方法是从1到1 000依次报价，肯定最终能找到答案。但是这会存在两个问题，一是时间上不可能允许你穷举1 000个数字；二是主持人提示你当前报价高低的这项服务就根本用不上了，因为你的这种竞猜方式只能是一直低于实际价格直到猜对为止。因此实际操作中不会有人使用这个办法。那么，有没有一种科学的竞猜方法可以使竞猜者一定能在规定的时间内猜出商品真实的价格呢？可以使用“折半竞猜法”解决这个问题，步骤如下：
（1）因为给定的价格区间是［1，1 000］元，所以，我们一开始可以选择猜这个区间的中间值，即500元。
（2）这时主持人会提示竞猜者所猜价格与商品实际价格的高低。因为商品的实际价格为625元，所以竞猜者猜到的价格一定是低了。
（3）这就说明实际的价格一定在（500，1 000］这个区间内，所以我们舍弃掉［1，500］这个区间，在（500，1 000］这个区间里继续猜价格。
（4）第二次猜价依然选择（500，1 000]这个区间的中间值，即750元。
（5）因为商品的实际价格为625元，所以主持人提示竞猜者价格高了。
（6）这就说明实际的价格一定在（500，750）这个区间之内，所以，我们舍弃掉［750，1 000］这个区间，在（500，750）这个区间里继续猜价格。
（7）第三次猜价依然选择（500，750）这个区间的中间值，即625元。
（8）这个价格恰好是商品的实际价格，因此猜价成功。
所以，对于这个价格的竞猜，我们仅需要猜三次便可以得到正确答案。
如果商品的价格不是625元而是其他价位，我们猜价的次数可能就不是三次了，或许会多一些，或许会少一些，但是使用这种“折半猜价”的方法确实可以很快地猜出实际的价格，这要比一个一个按顺序猜价效率高很多，也比漫无目标的“瞎猜价”更加有规律，更加有胜算的把握。
为什么使用这种“折半猜价法”能够以更快的速度猜到商品的实际价格呢？细心的读者一定会发现，我们每次猜价都是猜当前价位区间的中间值，然后主持人会提示你猜的价格与实际商品价格的高低，这样在下一轮的猜价中，价位区间就会缩小一半左右，也就是说问题的整体规模减小了一半左右。设 c 为当前猜价区间的长度（问题规模）， n 为猜价的次数， a 为最初的猜价区间长度（原始问题规模），那么使用折半竞猜法猜价，这三个量之间存在如下关系：
上式中符号
表示向下取整，例如
。因为
，
n
=1，2，3…不一定是整数，而价格区间的长度为整数，因此采用向下取整的方法得到新的价格区间长度。如果当前的价格区间长度为奇数，那么，下一次竞猜的价格区间长度就变为当前区间长度的1/2再向下取整。如果当前的价格区间长度为偶数，那么，下一次竞猜的价格区间长度就恰好变为当前区间长度的1/2。这个急剧缩小的趋势可以通过函数
的曲线图1-5表现出来。
图1-5 函数
的曲线
从上面这个式子中不难看出，每多一次竞猜，竞猜价格的区间长度就会变为原来的近1/2。这里面就存在一个指数爆炸的问题，随着 n （竞猜次数）的不断增大，（1/2） n 会急剧缩小，这样竞猜价格的区间也会随之急剧缩小。从上面这个例子中易见，最初的竞猜价格区间长度为1 000，仅仅经过两次猜价，其价格区间的长度就变为250。假设第三次还没有猜中，那么下一次竞猜的价格区间长度就变为125，接下来的价格区间长度就是62，31，15，7，3直到1。所以，对于本题，最坏的情况下我们也只需要竞猜10次就可以猜中商品的实际价格。
这样看来指数爆炸并不一定意味着是数据的加速膨胀，也可能是数据的急剧缩小。
现在又有这样一个问题：假设竞猜价格区间长度为 L ，如果采用折半竞猜的方法进行猜价，最坏的情况下需要竞猜的次数 n 是多少呢？
这个问题的详细推导可以借助计算机科学中的“二叉树理论”，在此不做展开，但是结论是明确的，即 L 和 n 之间存在如下关系：
例如本题中竞猜的价格区间长度为1 000，那么使用“折半竞猜法”，最坏情况下需要猜
次。
在这一点上，问题的初始规模越大，使用这种折半竞猜方法的优势就愈加明显。假设竞猜的价格区间为［1，1 500 000］元，区间长度为1 500 000，则最坏情况下仅需要猜20次便可以找到答案。竞猜的价格区间长度为原来的1 500倍，而最大的猜价次数仅为原来的两倍。
其实，“折半竞猜法”是由计算机科学中的“二分搜索法”演变而来的。所谓“二分搜索法”，就是在一个排列有序的包含 n 个元素的序列［ a 1 ， a 2 ，…， a n ］中寻找特定元素 x ，可以采用如同折半竞猜法的方式，先将 x 与序列中间的元素进行比较，再按照 x 与中间元素的实际大小选择在子序列［ a 1 … a n /2 -1］或者子序列［ a n /2 +1… a n ］中继续搜索。具体来说，如果 x 小于中间元素，则在［ a 1 … a n /2 -1］中继续查找，如果 x 等于中间元素，则查找结束；如果 x 大于中间元素，则在［ a n /2 +1… a n ］中继续查找。子序列的搜索方法与原序列的搜索方法相同。这里我们可以看到，使用“折半竞猜法”或者“二分搜索法”的前提条件是搜索的序列必须是按值有序排列的。在本题中，竞猜的价格区间本身是按值递增的，因此可以使用这种“折半竞猜法”进行价格的竞猜。