Question

解决一个问题的算法未尽只有一种。在考量用于解决同一个问题的多种算法的优劣时，可以认为转化为程序后，执行时间较短的算法更为优秀。虽然计算机的处理速度很惊人，但当处理的数据数值巨大或数量繁多时还是要花费大量的时间的。例如，判定91是否是素数的过程一下就有结果了，可是要判定999999937的话，笔者的计算机要花费大约55分钟了

有时稍微在算法中加入一些技巧，就能大幅度地缩短处理时间。在判定素数上，原先的过程是用待判定的数除以比较它小的所有正整数，只要加入一些技巧，改成用待判定的数除以比较它的1/2小的所有数，处理时间就会缩短。之所以改成这样是因为没有必要去除以比较它的1/2还大的数（要是从2开始依次除下去，只需要从2除到待判定数的平方根就足够了）。通过这点改进，除法运算的处理时间就能够缩短1/2

在算法技巧中有个著名的技巧叫作“哨兵”，这个技巧多用在线性搜索（从若干个数据中查找目标数据）等算法中。线性搜索的基本过程是将若干个数据从头到尾，依次逐个对比，直到找到目标数据。

下面还是通过例题来思考吧。假设有100个箱子，里面分别装有一个写有任意数字的纸条，箱子上面标有1-100的序号，现在要从这100 个箱子中找出是否有箱子装有写着要找数字的纸条

首先看看不使用哨兵的方法。从第一个箱子开始依次检查每个箱子中的纸条。每检查完一个纸条，还要再检查箱子的编号（用变量N表示），并进一步确认编号是否已超过最后一个编号了。这个过程用流程图表示如图5.6所示

图5.6 未使用哨兵的流程图

图5.6所示的过程，虽然看起来似乎没有什么问题，但实际上含有不必要的处理 – 每回都要检查箱子的编号有没有到100

为了消除这种不必要的处理，于是添加了一个101号箱子，其中预先放入的纸条上琯有正要查找的数字。这种数据称为“哨兵”，通过放入哨兵，就一定能找到要找的数据了。找到要找的数据后，如果该箱子的编号还没有到101就意味着找到了实际的数据；如果该箱子的编号是101，则意味着找到的是哨兵，而没有找到实际的数据。使用了哨兵的流程图如图5.7所示。

图5.7 使用了哨兵的流程图

需要反复多次检查的就只剩下“第N个箱子中包含要找的数字吗？”这一点了，程序的执行时间也因此大幅度缩减了

当笔者第一次得知哨兵的作用时，对其巧妙性感到惊叹，兴奋异常。有些读者会感到“不太明白巧妙在哪里”，那么就讲一个故事来解释哨兵的概念吧。假设某个漆黑的夜晚，在海岸的悬崖边上玩一个游戏，站在距悬崖边缘100米的地方，地上每隔1米放置一个物品，请找出这些物品中有没有苹果。

每前进1米就要捡起地上的物品，检查是否是苹果，同时还要检查有没有到悬崖边缘（不检查的话有可能掉到海里）。也就是说要对这两种检查反复若干次。

使用了哨兵后，就要先把起点挪到距离悬崖101米的地方，再在悬崖边缘放置一个苹果（如图5.8所示）

图5.8 使用了哨兵的游戏

这个苹果就是哨兵。每前进1米只需检查捡到的物品是不是苹果就可以了。如果捡到了苹果，只需站在原地再检查1米外的情况，如果还没有到悬崖边缘，就意味着找到了真正的苹果。如果捡到的是哨兵，说明已经到悬崖边缘了，而没有找到真正要找的苹果