标签归档:万物皆数

数学之美:从“二分法”到“万物皆数”!

二分法,就是一分为二的方法。

如我们两个人,共同吃一个苹果,通常我们会从中切开,然后一人一半。

除了日常使用之外,二分法还是一个非常高效的算法,它常被用作计算机的查找过程中。

#

为了说清楚二分法,我们先来玩一个猜数字游戏:

我心里默念一个1~64之间的数,你来猜是什么数,猜的过程中你可以向我提问,但是你只能问答案是“是”或“否”的问题。

为了保证不论在什么情况下都能以尽量少的次数猜中,你应该采取什么策略呢?

答案很显然,使用二分法!

我们先是猜是不是位于1~32之间,排除掉一半可能性,然后对区间继续二分。

这种策略,能够保证无论数字怎么跟你捉迷藏,都能在log_2{n}次以内猜中,用算法的术语来说就是它的下界是最好的。

为什么这种策略具有最优下界?答案也很简单,这个策略是平衡的。

反之,如果策略不是平衡的,比如问是不是在1~10之间,那么一旦发现不是在1~10之间的话就会剩下比N/2更多的可能性需要去考虑,简单的事情有可能会变得复杂。

这种采用二分法的策略的本质可以概括成“让未知世界无机可乘”。

它是没有“弱点的”,答案的任何一个分支都是等概率的。

反之,一旦某个分支蕴含的可能性更多,当情况落到那个分支上的时候你就郁闷了。

猜数字游戏最糟糕的策略就是一个一个的猜:

是1吗?是2吗?…

这种猜法最差的情况下需要64次才能猜对,下界非常糟糕,效率很低,而且结果具有随机性。

二分法为什么好,就是因为它每次都将可能性排除一半并且无论如何都能排除一半(它是最糟情况下表现最好的)。

继续阅读