浅谈算法分析的策略和技术

做算法分析的目的通常是为了确定算法的时间效率。这是通过对算法的基础步骤执行次数进行计数来完成的。对于几乎一切算法问题来说，计数的结果都是随着问题的规模增长的。而考察到底增长得有多快，才是算法分析的主要目的。而谈到计数，毫不奇怪地，就涉及数学了。所以，我们就从一些重要的数学公式入手，它们在算法分析中发挥的作用真是不可小觑。

1 几个求和公式，兼论算法效率

关于史上最伟大的数学家之一Carl Friedrich Gauss（1777—1855），有一个众所周知但真实性可疑的故事，那就是当他10岁左右的时候，他的老师要求全班同学计算前100个正整数之和，即的值，他可能觉得这会花费这些学生相当一段时间。当然，老师没有想到这些学生中隐藏着一位数学高手。理所当然地，Carl只花了几分钟就得到了答案，方法是把全部数字分成50对，其中每一对都有着相同的和101：

把这种思路推广到前个正整数，就得到了下面的公式：

（1）作为练习，建议读者尝试求解谜题心算求和，其中就利用了本公式及其变形。

公式(1)在算法中有着无可取代的地位。还可以从它推导出若干其他的有用公式。比如，欲求前个正偶数的和，我们就可以得出：

而前个正奇数的和，则这样推导：

另一个非常重要的公式是2的各次方幂之和，我们在概论的前半部分已经用过：

（2）现在我们来看第一道采用算法分析求解的谜题。

据说，国际象棋游戏是很多个世纪以前由印度西北部的一位叫Shashi的贤人发明的。当Shashi将他的发明呈献给国王以后，国王爱不释手，并承诺给予这位发明人任何他想要的赏赐。Shashi说自己想要一些麦子，不过他是这么说的：在国际象棋棋盘的第1个格子里放1粒麦子，第2个格子里放2粒，第3个格子里放4粒，第4个格子里放8粒，依此类推，直至64个格子被放满为止。请问，这样的赏赐要求合理吗？

根据公式，Shashi要求的麦子总粒数等于：

如果每一秒可以数一粒麦子的话，这个总数的数量需要花费5850亿年才能数完。这比已知地球年龄的100倍还要长。这个例子很好地说明了指数增长（exponential growth）有多么恐怖。显然，如果一个算法要求指数增长，那么除了极小的谜面以外，对于大多数情况它都没有实用性了。

如果Shashi要求的不是每格比前一格麦子粒数加倍，而是每格比前一格麦子粒数多两粒呢？这样，麦子的总粒数就等于：

假如还是每一秒可以数一粒麦子的话，只需要1小时14分钟，他要求的合理赏赐就能够数完了。二次（quadratic）增长，显然作为算法运行时间的增长速率来说，是较能够接受的。

线性（linear）算法运行得相对较快，这种算法和输入规模成比例地增长。还有更快的对数（logari thmic）算法。这种类型的算法通常基于每次降低一个常数因子的减而治之策略（参见概览的算法设计策略部分），比如，反复地将问题规模减半。这样，指数增长就被反其道而用之，问题的规模会急剧下降。前半部分的猜数字谜题就属于对数算法类型。

2 非递归算法分析

读者可能不会为以下的事实感觉意外：非递归算法（nonrecursive algorithm）就是指没有形成递归的算法。换言之，求解这种算法，不能通过将其自身应用于同一问题越来越小的谜面，最终达到一步解出的目的。非递归算法的典型分析方法，就是对它的主要步骤数目求和。然后，将该和简化为一个精确的计数公式，或一个表达其增长速率的估算公式。我们来看看下面这个例子[Gar99, p. 88 J，一个像谜题的问题。

算法起始时，只有一个单位方块。每步迭代都在上一步的外围填满方块。试问，在第步迭代时，总共有多少个单位方块？最初几步迭代如图1所示。

图1方块搭建算法的最初几步迭代示意

算法的基本步骤，就是添加一个单位方块。因此，对算法的基本步骤的数目进行计数，实际上就等价于对单位方块的总数进行计数。经过步迭代以后，最长的水平行将有个这样的方块，位于其上下的其他行将各包括从1到的所有奇数，由于前个奇数之和等于，单位方块的总数就等于：

另一种解法是，注意到在第步（）迭代时，增加的单位方块个数等于。这样，经过步迭代，单位方块总数可以这样计算：

虽然采用中规中矩的标准技术当然不会有错，但是利用题设的特殊性却总是有用的。就拿这道题来说，就可以对n步迭代以后产生图形的对角线所包含的方块数目进行计数。这样就可以发现，图形是由n条每条都包含了n个单位方块的对角线和交替出现的(n-1)条每条都包含了(n-1)个单位方块的对角线共同构成的，所以，总计有图像说明文字个单位方块。

3 递归算法分析

我们将通过解答经典的汉诺塔谜题，来展示递归算法分析的标准技术。

本谜题的一般谜面是有个大小不同的圆盘，以及三根桩。一开始所有的圆盘都按大的在下、小的在上的顺序摆放在第一根桩上。目标是通过一系列的移动，将所有圆盘都移到另一根桩上去。每次只能移动一个圆盘，并且不能违反大的在下、小的在上的规定。

这个问题有个优雅的递归解法，如图2所示。欲将个圆盘从1号桩转移至3号桩上（2号桩作为辅助桩），则先将个圆盘从1号桩转移至2号桩上（3号桩作为辅助桩），再将最大的一个圆盘从1号桩直接移动到3号桩上，最后把个圆盘从2号桩转移至3号桩上（1号桩作为辅助桩）。当然，如果，把唯一的这个圆盘从1号桩直接移动到3号桩上即可。

图2 汉诺塔谜题的递归解法

显然，算法的基本操作是将一个圆盘从一根桩移动到另一根桩上去。令M(n)表示算法在处理个圆盘时所要求的移动步骤总数。那么，根据上面的算法描述（同时也请参考图1.13），我们就可以得出下面关于M(n)的方程：

，当n>1时

上式可化简为

，当n>1时

这样的方程称为递归关系式（recurrence relalion），因为它们表明了数列的第项与它的前项之间的关系。具体到这道题目，数列的第项，即M(n)，比它的前一项M(n−1)的两倍还要多1。请注意，这样的数列并不唯一，因为此时还没有指定数列的首项。由于算法指定在仅有一个圆盘时，仅须移动一步，题目就可得解，所以我们就能够为递归关系附加一个条件，即M(1)=1。毫不奇怪，这个条件就称为初始条件（initial condition）。把以上分析综合一下，我们就得出了个圆盘条件下的汉诺塔谜题所对应的递归关系式及其初始条件：

M(n)=2M(n-1)+1，当n>1时，

M(1)=1。

在这里，我们不采用概览的前半部分介绍过的标准方法来求解这个方程，而是尝试用归纳法：先利用上述方程算得M(n)最开始若干项的值，并列成表格，尝试找出通用模式，然后证明这个模式适用于所有的正数n。

考察M(n)最开始若干项的值以后，我们发现似乎有公式图像说明文字成立。显然，有图像说明文字。证明该公式对一切n>1皆成立的最简单方法就是把公式本身代入方程，看看是否对一切符合大小的方程都成立即可。结果证明的确如此，因为：

因此，我们就得到了一个指数算法，这就是说即使对于不太大的，算法的运行也会花费长得难以想象的时间。究其原因，并不在于该特定算法本身设计拙劣，并不难证明，对于这个问题来说，该算法已经是所有可能的算法中最高效的。是问题内在的困难性，使得解决它的尝试有了指数级别的难度。但这未必不是好事：在汉诺塔谜题的发明者Édouard Lucas在19世纪80年代发表的最初版本中，梵天之塔的僧侣们在移动完64个圆盘以后，世界即将毁灭。假设僧侣们不吃、不睡、不死，并且每分钟移动一个圆盘的话，世界将在约图像说明文字年毁灭，这个时间比估算的宇宙年龄要长约1000倍。

作为练习，读者也许愿意动手求解谜题受限的汉诺塔中的最小移动步数，这是诸多经典版本的变形之一：

4 不变量

我们以不变量的思想作为概览部分的压轴话题。在我们的讨论中，所谓不变量（invariant），就是在任何一个算法在解题时保持不变的某种性质。对于谜题一般的问题而言，不变量经常用来说明某个问题无解，因为称为不变量的性质在谜题的初始状态成立，而在所要求的终止状态却并不成立。我们来看一些例子。

缺角棋盘的多米诺铺陈 是否可能用多米诺骨牌1铺满一块缺了一个角的棋盘（如图3（a））？是否可能用多米诺骨牌铺满一块缺了对角线上的两个对角的棋盘（如图3（b））？

图3（a）缺了一个角的棋盘 （b）缺了对角线上的两个对角的棋盘

第一个问题的答案肯定是“不行”：任何多米诺铺陈都只能覆盖偶数个方块（覆盖方块的偶数配对特性就是这里的不变量），而第一个问题中的棋盘上的方块数是一个奇数。

第二个问题的答案也是“不行”，尽管题设棋盘上的方块数显然是偶数。涉及的不变量并非同一个：由于一块多米诺骨牌会覆盖一明一暗两个方块，所以在任何多米诺铺陈中覆盖的明暗方块数都是一样多的。这么一来，能够覆盖题设中棋盘的多米诺铺陈就不可能存在了，因为明暗方块数由于缺了对角线上两个对角，而相差了两个。

一般地，奇偶配对（even-odd parity）以及着色（coloring），是运用不变量思想时用得最广的两种方法。谜题“最后一个球”和“骑士的征途”是两个典型应用例子，读者可以参考。

不变量的另一种重要性可以在另一道关于在古老的普鲁士城市哥尼斯堡中如何散步的著名谜题中得到体现。

是否可能在单次散步中，过哥尼斯堡的所有桥仅一次，并返回起点？河流、两座小岛以及七座桥的草图如图4所示。

图4连接陆地和两座小岛，并供人过河的哥尼斯堡七桥

著名的瑞士数学家Leonhard Euler（1707—1783）解出了本题。首先，Euler注意到，经过的陆地——无论是河岸还是小岛——都和问题求解无关。唯一有关的，是桥建立起来的连接。用现代术语来说，就是这种洞见成功地使他把原问题变换成了一个图论问题，如图5所示。（事实上，该图是一个多重图，因为连接图的某些顶点的，可能不止一条边。）

图5 表达哥尼斯堡七桥问题的多重图

问题就在于图5中的这个多重图中是否存在一条Euler回路：一个邻接顶点的序列，它在回到起始顶点前遍历了所有的边仅一次。Euler注意到，符合这种要求的回路中，进入一个顶点的次数必须恰好等于离开该顶点的次数。所以，若要多重图中存在这种回路，就必须满足接触顶点的边数——称为该顶点的度数——对于所有的顶点而言皆为偶数。这个不变量性质就决定了哥尼斯堡七桥问题无解，因为条件不满足：图5中所有的顶点度数都为奇数。更有甚者，基于同样的分析，可以发现即使不要求回到起点，散步时想要过每座桥仅一次也是不可能的。若要实现这种散步路线（称为Euler路径），除起点和终点这两个顶点外，其他所有顶点的度数都必须是偶数。

顺便指出，连通多重图中若要存在Euler回路和Euler路径，则上述条件不仅是必要的，也是充分的。（如果说一个多重图是连通的，就意味着每对顶点之间都存在一条路径。当然，如果这一点不成立，Euler回路和Euler路径的存在性也就无从谈起了。）这个事实首先是由Euler发现的，但后来由另一位数学家证明。读者可以利用以上分析来求解正文部分的谜题一笔画。

如今，哥尼斯堡七桥问题已经成为学习图论这门计算和运筹学学科的重要分支必读的内容。人们也经常以它为例，来说明解谜活动在严肃科学、教育和实际应用中的潜在用途。

下面这道谜题里，不变量将扮演一个不同的角色，不再用来证明解不存在。

求将n×m格的巧克力条掰成nm块的最少次数，每次只允许沿着纵横方向掰，且每次只能掰一个碎块。

读者不妨亲手尝试一下这道数学家和计算机科学家们都会做的谜题，再看下面两句话揭开的谜底。由于一次只能掰一个碎块，而每掰断一次只会让碎块数增加1，所以要把n×m格的巧克力条掰成nm块，就需要掰(nm-1)次。而且，只要沿着纵横方向，无论怎么掰次都能把n×m格的巧克力条掰成nm块。

我们举的最后一个例子中，不变量将扮演一个更具建设性的角色，它将指明算法运行的必由之路。下面的谜题由史上最著名的两位制谜人Henry E. Dudeney [Dud02, p. 95]和Sam Loyd [Loy59, p. 8]分别发表在两处2。这道题目的所有变形都不过是把方格数目和表述文字简单变化一下而已。

用一块的棋盘表示一片田地，用同一种颜色的两枚棋子表示一个农夫和他的妻子，用同一种其他颜色的两枚棋子表示一只公鸡和一只母鸡。每次移动棋子都可以把它移到上下左右任一方向的相邻位置，但不能移到对角线的相邻位置。如果起始位置如图6（a）所示，然后按照农夫、农妇、公鸡、母鸡的顺序依次移动各个棋子，直到鸡被人捉住为止，即人再移一步即占据鸡的位置。试用最少移动步数完成题设任务。

我们很快就会发现，农夫捉不到公鸡，农妇捉不到母鸡。将棋盘按国际象棋棋盘进行着色以后，我们就能看出来，只有人和鸡在相邻的两个颜色不同的格子里的时候（见图6（b）），人才能捉到鸡。但是，农夫和公鸡、农妇和母鸡分别是从相同颜色的格子里出发的，这个性质在移动任意有限步以后仍然保持。所以，农夫应该去捉母鸡，而农妇应该去捉公鸡。即使鸡不配合，它们也不能避免这样的宿命：一只在八步以后被捉，另一只在九步以后被捉。

图6（a）谜题田地里的鸡题设的棋盘（b）将棋盘着色后的结果

至于某个具体谜题应该应用哪个策略来求解，这个问题没有答案！（如果有的话，谜题也就失去益智娱乐的魅力了。）策略只是通用工具，对于特定的谜题来说，策略可能管用也可能不管用。经过大量的实践以后，才能对策略的有效性产生一些直觉，但这样的直觉当然不可能万无一失。

还有，以上讲述的策略和技术为具备算法背景的谜题提供了一套极有用的工具集。

当然，即使已经知道要应用哪种策略，求解过程也可能仍然远非易事。比如，运用不变量来证明某个谜题无解是一种惯用手法。但是即使已经知道奇偶配对以及棋盘着色可能有利于导向答案，发掘出一个特定问题的不变量却可能仍然很困难。还是那句话，多多练习，解题任务就会变得更顺手，但难度不一定很小。

本文节选自《算法谜题》

本文转载自异步社区。

Python

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。