首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》讨论1:对数级算法的性能

关灯直达底部

一个酒保和顾客打了一个10 000美元的赌。“我将选择一个从1~1 000 000的数字,然后你能够每次猜1个数字,共猜20次;每一次猜过之后,我将会告诉你高了,低了或者是你赢了。如果你能在20个问题之内赢,我给你10 000美元,否则你给我10 000美元。”你会打这个赌吗?你也许会,因为你可以一直赢下去。表2-1给了一个场景,不过候选数字是从1~10。问一系列的问题,并且每个问题都把候选数据缩减了一半。

每次根据酒保的回答,将可能的数字范围缩减一半。最后,可能的数字只剩下了一个;这种情况将会在[log(n)]次询问之后出现。将[x]归入到等于或者大于x的最小整数。例如,如果酒保选择了数字范围是1~10,那么你最多只需要猜测[log(10)]=[3.32],即4次。

这种方法在1 000 000个数字的时候也同样可行。事实上,例2-1所示的猜数算法能够对于任何的范围[low,high]有效,并且在[log(high-low+1)]次猜测之后得到数字n。如果有1 000 000个数字,那么这个算法将在至多[log(1 000 000)]即[19.93],也就是说20次(最坏情况)知道是哪个数字。

例2-1:在范围[low,high]之间猜数字的Java代码

对数级算法是非常高效的,因为它们能够快速收敛到解。一般来说,这些算法的成功之处在于它们每次将问题的规模缩减一半。这个猜测算法至多经过k=[log(n)]次迭代便可以得到解,在第i次(i>0)迭代的时候,算法在±ε=2k-i个数中进行猜测。ε可以看做是不确定的个数。在每一次迭代之后,ε缩减一半。

另外一个例子中则展现了牛顿法如何高效地解决一元方程(也就是说,x取什么值,使得f(x)=0)。解x*sin(x)-5*x=cos(x),设f(x)=x*sin(x)-5*x-cos(x),其导数为f'(x)=x*cos(x)+sin(x)-5-sin(x)=x*cos(x)-5。牛顿迭代计算出xn+1=xn-f(xn)/f'(xn)。开始猜测x等于0,这个算法能够快速地给出一个正确解,x=-0.189302759,见表2-2。被用括弧围起来的二进制和十进制数表示精确位。