知其所以然（以算法学习为例）

yulzhu

By 刘未鹏

Updated(2008-7-24)：更新见正文部分，有标注。

其实下文的绝大部分内容对所有学习都是同理的。只不过最近在正儿巴经地学算法，而后者又不是好啃的骨头，所以平时思考总结得就自然要比学其它东西要多一些。

问题：目前几乎所有的算法书的讲解方式都是欧几里德式的、瀑布式的、自上而下的、每一个推导步骤都是精准制导直接面向目标的。由因到果，定义、引理、定理、证明一样不少，井井有条一丝不乱毫无赘肉。而实际上，这完全把人类大脑创造发明的步骤给反过来了。看起来是阳关大道，实际上车马不通。


而对读者来说，这就等于直接告诉你答案&做法了，然后让你去验证这个答案&做法是可行&成立的。而关于答案&做法到底是怎么来的，从问题到答案之间经历了怎样的思维过程。却鲜有书能够很好的阐释。就我有限的阅（算法）书经验，除了波利亚的《怎样解题》还算合格之外（也并非最理想），其它的（包括有名的《算法导论》、《如何解题：现代启发式方法》、《Algorithms》、《编程珠玑》，甚至TAOCP——公平地说由于高老大对算法领域历史了解得非常通透，所以许多地方能够从原始脉络来讲述一个问题，譬如令人印象深刻的从竞赛树到堆的讲解就寥寥一页纸道出了堆这个数据结构的本质来，而像刚才列的几本有名的书却都没有做到），在思维的讲述上都算不上合格（当然不是说这些书没有价值，作为知识性的参考书籍，它们将知识整理出系统结构，极大的便利了知识的掌握，就像《什么是数学》所做的工作一样），为什么我这么说呢，因为我发现每每需要寻找对一个算法的解释的时候，翻开这些书，总是直接就看到关于算法逻辑的描述，却看不到整个算法的诞生过程背后的思想。

我们要的不是相对论，而是诞生相对论的那个大脑。我们要的不是金蛋，而是下金蛋的那只鸡。

Update(2008-7-24): 收到不少同学的批评，想来这个开头对一些著作的语气过重了，实际上，注意，我完全不否认这些著作的价值，我自己也在通过阅读它们来学习算法，并且有很多收获。这篇文章更多的只是建议除了阅读这些著作之外还需要做的功课。此外，对于这类知识讲述（欧几里德）方式的批判西方（尤其是在数学领域）早就有了，早在欧拉和庞加莱的时候，他们俩就极其强调思维的传授，欧拉认为如果不能传授思维，那数学教学是没意义的。而庞加莱本人则更是对数学思维有极大的兴趣和研究（我前阵子在讨论组上还转载了一篇庞加莱的著名演讲，就是说这个的，参见这里）。我只是在说目前的算法书没有做到思维讲述的层面，因此建议阅读这些书之余应该寻找算法的原始出处，应该寻根究底，多做一些功课，知道算法到底是怎么诞生的，并且我说明了为什么应该知其所以然，有哪些好处（见下文），我还给了几个例子譬如红黑树作者讲红黑树的，g9讲后缀树的，以及Knuth讲heap 的。唉，其实挺正统的观点，授人以渔，不管是东方西方都有类似的古老谚语。而我只是从认知科学的角度加了点解释，windstorm称之为“解释文”。而已。可惜被开头的语气搞砸了，算了，既发了也就不改了。


为什么会这样，其实是有原因的。

我们在思考一个问题的过程中有两种思维形式：

* 联想：这种思维某种程度上可以说是“混乱”的（虽然从一个更根本的层面上说是有规则的），所谓混乱是指很多时候并不确定联想到的做法最终是否可行，这些联想也许只是基于题目中的某个词语、语法结构、问题的某个切片、一些零星局部的信息。这个过程是试探性的。最后也许有很大一部分被证明是不可行的。很多时候我们解决问题用的都是这种思维，简言之就是首先枚举你关于这个问题能够想到的所有你学过的知识，然后一一往上套看看能否解决手头的问题。这种思维方式受限于人脑联想能力本身的局限性。我在《跟波利亚学解题》中就提到了几个例子。联想本身需要记忆提取的线索，所以受到记忆提取线索的制约，如果线索不足，那怎么也联想不起来。而提取线索的建立又取决于当初保存记忆的时候的加工方法（《找寻逝去的自我》里面有阐述），同时，面对一个问题，你能够从中抽取出来的联想线索又取决于你对问题的认识层度/抽象深度，表浅的线索很可能是无关的，导致无效的联想&试错（《Psychology of Problem Solving》里面有阐述）。总之，联想这个过程充满了错误的可能。
* 演绎&归纳：演绎& 归纳是另一种思维形式。它们远比联想有根据。其中演绎是严格的，必然的。归纳也是有一定根据的。在面对一个问题的时候，我们有意无意的对问题中的各个条件进行着演绎；譬如福尔摩斯著名的“狗叫”推理——狗+生人=>吠叫 & 昨晚狗没有叫 => 那个人是熟人。就是一个典型的对问题的各个条件进行演绎的推理过程。还有就是通过对一些特殊形式的观察来进行归纳，试图总结问题中的规律。然而，不幸的是，面对复杂的问题，演绎&归纳也并不总是“直奔”问题的解决方案的。人的思维毕竟只能一下子看到有限的几步逻辑结论，一条逻辑演绎路径是否直奔答案，不走到最后往往是不知道的，只要答案还未出现，我们大脑中的逻辑演绎之树的末端就始终隐藏在黑暗之中。而当最终答案出现了之后，我们会发现，这棵演绎之树的很多分支实际上都并不通往答案。所以，虽然演绎&归纳是一种“必然”的推理，然而却并不“必然”引向问题的结论，它也是试错的，只不过比联想要更为靠谱一些。

既然认识到，人类解决问题的两大思维方式实际上都是有很大的试错成分的（好听一点叫“探索”），那么就不难意识到，对一个问题的思考过程实际上是相当错综复杂的，而且充满了无效分支——在思考的过程中我们也会不断的对分支进行评估，做适当的剪枝——因此当我们找到问题的解之后，一来思维的漫长繁杂的过程已经在大脑里面淡化得差不多了，只有那些引向最终结论的过程会被加“高亮”——我们在思考的过程中本就会不断的抛弃无效的思路，只留下最有希望的思路。简而言之就是最后证明没用或者早先我们就不抱希望的一些想法就被从工作记忆中扔掉了。二来，思考过程是我们的空气和水，而“鱼是最后一个感觉到水的”，我们感觉不到思维法则本身的存在，我们只是不知不觉运用它。三来，由于我们的目标是问题的解，解才是我们为之兴奋和狂喜的东西，而不是求解的过程，过程只是过程，目的才是目的。这就像一个寻宝者，在漫长曲折的寻宝历程之后，在找到宝藏的时候，他会对宝藏感到狂喜（记得阿基米德的“找到了！”吗？）而迫不及待地要展示出来，而漫长的思考本身却成了注脚。我们是有目的的动物，目的达到了，其它的就相对不那么重要了。最后，对于传授知识的人，也许还有其四：感到介绍思维过程是不相干的，毕竟思维过程并不是算法问题的解，算法问题的解才是算法问题的解。然而不幸的是，忽视到达解的那个过程实际上却变成了舍本逐末。我们看到的是寥寥数行精妙绝伦的算法，然后仰天长叹自己想不出来啊想不出来。为什么想不出来，因为你不知道那短短数行算法背后经历的事怎样漫长的思考过程，如果问题求解是一部侦探小说，那么算法只是结局而已，而思考过程才是情节。


既然如此，也就难怪古往今来算法牛人们算法牛，但却没有几个能真正在讲述的时候还原自己的思维过程的（那个“ 渔”字），手把手的教学生走一遍推理的思路，就可以让学生获得思维过程的训练。金出武雄在《像外行一样思考，像专家一样实践》中说写论文应该写得像侦探小说一样，我很赞同。欧几里德式的介绍，除了提供枯燥的知识之外，并没有提供帮助人获得知识的东西——思维（关于对数学书籍的欧几里德式写法的批评其实也是由来已久了，并且有人呼吁了好几种其它的教学方法）。从这方面，我们所尊敬的一些“圣经”级书籍在传道授业上还不如侦探小说，前者是罗列一大堆知识，后者则是阐述获得知识的过程——推理&联想。

然而，我们都是人，人类该有的思维形式，我们难道不是都有吗。既然如此，思维本身又有什么需要一遍遍教的呢？

并非如此。

讲述思维过程而非结果有几个极其重要的价值：

* 内隐化：思维法则其实也是知识（只不过它是元知识——是帮助我们获得新知识的知识）；是内隐的记忆。我们在思考的过程中觉察不到思维法则的作用，它们却在幕后实实在在的左右着我们的思维轨迹。要将思维方法内隐化，需要不断练习，就像需要不断练习才能无意识状态下就能骑自行车一样。
* 跨情境运用：思维法则也是知识记忆，是问题解决策略。既然是记忆，就受到提取线索的制约，这就是为什么当波利亚告诉你要“注意未知数”之后你还是不能真正在所有需要你“注意未知数”的地方都能提醒自己“注意未知数”。很多时候未知数是很隐蔽的，未知数并不会总是头顶一个大帽子上面写着“我是未知数”。所以很多时候缺乏对这个策略的“提醒”线索，这也是为什么你学会了在解决数学问题的时候“注意未知数”却不一定能在解决现实生活中的问题中时刻都能“注意你的未知数”（《你的灯亮着吗？》整本书的价值便在于此），因为解数学题和解决生活中问题的场景不一样，不同的环境线索，在你大脑中激发的记忆也不一样。就连问题求解中，不同的问题之间的细小差别也可能导致思维轨迹很大的不同，有时你的注意力会被一个无关线索激发的联想吸引开去，忘记如“注意你的未知数”这样的重要法则。而一本从思维角度来讲问题求解的书则可以一遍遍将你置于不同的问题场景下然后在该提醒你的时候提醒你，让你醒悟到“哦，原来这个时候也应该想到这个啊。”，做多了这样的思维演习你就会逐渐从中领悟到某种共性，并将一些思维习惯得到强化，于是终于能够在需要运用某策略的时候能适时的想起来了。
* 对问题解的更多记忆提取线索：我们平时学习算法时几乎仅止于“理解”，别人把一个方案放在你面前，你去验证一下，心说“哦，不错，这个的确可以工作”。然后就没了。稍微简单一点的算法还好，复杂一点的对于记忆的负担是很大的，这就是为什么有时候我们看到一个绝妙的解法，这个解法看上去不知道从哪里来的，但经过我们的理解，却发现是对的，我们感叹，真巧妙，结果一些天之后，别人问起这个问题，我们说：“唉，那是个多么巧妙的算法啊，但是我只记得它巧妙，却不记得它到底是怎样的了。” 为什么？因为在不知其所以然的情况下，算法只是一堆离散的机械步骤，缺少背后的思想的支撑，这些步骤之间就没有一个本质层面上的关联（先知亚里士多德早就指出：学习即联接）。所以就跟背历史书也没多大区别。然而，知道了算法是怎样一步步被推导出来的，我们就一下拥有了大量的记忆提取线索：对算法发现过程中的任何一个关键步骤（尤其是本质）的回忆都可能使我们能够自己动手推导出剩余的内容。譬如你知道堆(heap)是怎样由朴素的决策树演化而来的，它又是为了解决什么问题的，你即便忘记了具体的细节，也可以自己推导出来。譬如你知道KMP算法的本质在于消除回溯，至于如何消除回溯却并不是那么难以推导的，所以即便忘了也可以借助于大脑的逻辑演绎能力再现出来。譬如你知道Tarjan算法其实只是从后序遍历经过两个优化调整而来的（其中并査集的使用其实只是优化手段——为了能够迅速判断祖先节点是谁——而非算法本质 ——当然，算法设计的主要任务本来就是通过问题条件中蕴含的知识来“消除冗余计算”和“避免不必要计算”，所以你也可以说并査集的使用是关乎本质的，只不过，知道了为什么需要引入并査集，就会强烈地感觉到一切是顺理成章的了），那这个出了名的绕人的算法也就不那么难以理解和记忆了。譬如你知道排序的本质，就能够对什么是最优排序，为什么它是最优排序有深刻的认识。四两拨千斤。


* 包含了多得多的知识：记一个算法，就只有一个算法。一个萝卜一个坑。就好比背99乘法表只能解决乘法问题一样。而记背后的思想，却有助于解决一类问题。思想所处的抽象层面往往比到处都是实现细节的算法本身要低，越是低的抽象层次，越是本质，涵盖范围越是广泛。数学的发展本身就体现了这个过程，抽象代数就是非常好的例子。算法诞生过程中的思路往往包含了比实际算法更本质得多的知识，实际算法乃至算法的某个特定语言的实现包含了太多表面的不相干知识，它们会阻碍对本质的理解。
* 重在分析推理，而不是联想：学了一大通算法和数据结构之后的一个副作用就是，看到一个问题之后，脑袋里立即不管三七二十一冒出一堆可能相干的数据结构和算法来。联想是强大的思维捷径，在任何时候都会抢占大脑的工作记忆，由不得你控制——比如我问你“如何寻找区间的最大值”，首先进入你的意识的肯定就是学过的那个算法，甚至算法的实现细节都一一跳了出来，也许最先跳出来的还是算法实现中某个最容易弄错的边界细节，或是某个比较tricky的实现技巧！然而这些其实根本不反映一个算法的本质，结果想来想去总是停留在问题的表层。而另一方面，重在思维的传授则可以让人养成从问题本质入手，逐步分析推理的习惯，而不是直接生搬硬套。当然，完全不可否认，联想本身也是极其重要的思维方法，甚至可以说是人类思维最重要的特征。很多时候我们并不知道问题的本质是什么，就需要靠联想、类比来领路探索。只不过，养成优先从问题的本质入手进行考察的好习惯绝对是有更大的好处的。

那到底什么样的才算是授人以渔的呢？波利亚的《如何解题》绝对算是一本，他的《数学的发现》也值得一看。具体到算法书，那就不是光看text book就足够的了，为了深入理解一个算法的来龙去脉前因后果，从一个算法中领悟尽量深刻的东西，则需要做到三件事情：

* 寻找该算法的原始出处：TAOCP作为一个资料库是绝对优秀的，基础的算法只要你能想到的，几乎都可以在上面找到原始出处。查到原始出处之后（譬如一篇paper），就可以去网上搜来看了。因为最初的作者往往对一个方案的诞生过程最为了解。比如经典数据结构中的红黑树是出了名的令人费解的结构之一，但它的作者Sedgewick一张PPT，给你讲得通通透透，比算法导论上的讲法强上数倍。
* 原始的出处其实也未必就都推心置腹地和你讲得那么到位：前面说过，算法设计出来了之后人们几乎是不会去回顾整个的思维过程细节的，只把直指目标的那些东西写出来。结果就又是一篇欧几里德式的文章了。于是你就迷失在一大堆“定义”、“引理”、“定理”之中了。这种文章看上去整个写得井井有条，其实是把发明的过程整个给颠倒过来了，我一直就想，如果作者们能够将整个的思路过程写出来，哪怕文字多上十倍，我也绝对会比看那一堆定义定理要容易理解得多。话说回来，怎么办？可以再去网上找找，牛人讲得未必比经典教材上的差。那倘若实在找不出好的介绍呢，就只能自己揣摩了。揣摩的重要性，是怎么说都不为过的。揣摩的一些指导性的问题有：为什么要这样（为什么这是好的）？为什么不是那样（有其它做法吗？有更好的做法吗？）？这样做是最好的吗？（为什么？能证明吗？）这个做法跟其它的什么做法有本质联系吗？这个跟这个的区别是什么？问题的本质是什么？这个做法的本质又是什么？到底本质上是什么东西导致了这个做法如此..？与这个问题类似的还有其它问题吗？（同样或类似的做法也适用吗？）等等。
* 不仅学习别人的思路，整理自己的思路也是极其重要的：详见《跟波利亚学解题》的“4. 一个好习惯”和“7. 总结的意义”。

前一段时间我们讨论组上有不少例子，见这里，或这里。

yulzhu

查了一下，上篇知其所以然（以学习算法为例）是08年7月写的，现在已经是10年11月，过去了两年零4个月，这说明了三件事情：1，一个问题其实你可以一直放在脑子里面，利用暗时间对其软泡硬磨，时间足够久你总会有一点新的感悟，问题其实就像那句老话说的那样，不怕贼偷就怕贼惦记，聚精会神的思考一天，也许比不上惦记一个星期（据说数学家庞加莱就特别会惦记问题）。 2，事实上，当你感觉懂了的时候，你至少得反问自己一句，真的懂了吗？当你确信自己真的懂了的时候，你至少得讲给别人听，别人听懂了吗？考察你自己是否真懂了的一个很好的依据是，你是否有一种“哦，原来是这样啊，这下再也不可能忘记了”的感觉。3，我其实没有忘记这个博客。如我之前说的，记录只是学习和思考的副作用，只要还在学习和思考，就必然会有新的记录。

我有一个习惯，看定理必看证明。一个你不明白其证明的定理在我看来比不知道这个定理还要糟糕，因它给你造成一种懂了的错觉。在没有明白背后的证明之前，任何一个定理对你来说都是等价的——等价于背乘法口诀（只不过有的长一点有的短一点）。一个原本美妙的定理，把其证明扔掉就是真正的买椟还珠，暴殄天物。

从现实意义来说，去理解一个定理的证明会带来巨大的好处，首当其冲的好处就是你很难再忘掉它。这一点其实很容易解释——在理解一个定理的证明之前，定理对你而言是一堆没有内在联系的词句，而在理解了证明之后，定理就归约为证明它所需的条件加上逻辑，“逻辑”本来就存在于你的大脑里面，而证明的过程中除了公理和用到的常见定理（往往没几条）之外，宽泛地说，需要你去记的，一般来说也只有一个或两个关键的insights，也就是我们常说的证明中的神来之笔，比如几何证明里面的某条看上去莫名其妙的辅助线，一旦你知道了这条辅助线，那么整个证明就毫无难处，那么该定理的信息量便直接缩减为一条辅助线的信息量；虽然看上去这一步信息并没有缩减多少，但是如果你考虑到类似的辅助线不仅会用在这个特定的定理上，往往会在很多地方用到。很多关键的证明手法是通用的。那么其实你就是把所有以这个辅助线为关键证明手法的定理的集合的信息量归约为了这条辅助线。如果你进而甚至能够理解了作这条辅助线的思想精髓，那就更牛逼了，因为解决问题的思路更具有一般性，理解了寻找正确的辅助线的思路，你就根本不需要去记得某条特定辅助线的作法，你就把所有以作一条或几条辅助线为证明核心的定理的集合的信息量归约为了这个“寻找辅助线的思路”。

这是一个树状的知识结构，越往上层走，需要记忆的节点就越少。所谓触类旁通者，其实便是因为他擅长去理解解法背后的更具一般性的东西。所以我还有一个习惯，就是看到美妙的证明和解法总是会去一遍又一遍的去反复揣摩，试图理解想出这个证明的人到底是怎么想出来的，有没有什么一般性的方法可循，很多时候，在这样揣摩的过程中，你会理解到更深刻的东西，对问题性质更深刻的认识，对解决问题的思路更深刻的认识，这些认识不仅对于你理解当前这个定理或问题有极大的帮助，同时也有助于你解决以后会遇到的表面不同但本质一样的问题。

与看定理必看证明类似，看一个问题的解法，必然要看解法所诞生的过程，背后是否隐藏着更具一般性的解决问题的思路和原则。否则一个解法就只是一个问题的解法，跟背口诀一样。即便记住了也无法推广，即便当时记住了也容易遗忘。

举个经典的例子：每本算法书都会讲动态规划，每本讲动态规划的书都会讲背包问题，每次讲背包问题都会讲可重复背包和01背包，我们就拿《Algorithms》这本还算不错的算法书对背包问题的讲解来说吧，重复背包问题的递归公式是这样的：

K(W) = max { K(W-Wi) + Vi : Wi <= W }

这个公式的理解倒是很简单：为了把问题降阶，我们在最终的最优解里面去掉一个元素，对这个元素的可能性进行讨论，它必然是任何Vi之一（前提是Wi <= W，否则就装不下），而在去掉这个元素之后，剩下的元素肯定构成问题 K(W-Wi) 的最优解，于是递归关系出现了。

此外也可以这样来理解：要拿一组最优元素，那么总得开始一个个拿吧，对第一个拿的元素进行讨论，而问题的最优解等于讨论的各个分支的最优解中的最优者；如果拿掉Vi之后，剩下来要怎么拿才能最优呢？这就是一个 K(W-Wi) 的问题了。

01背包问题就大不一样了——每个物品都只有一件，拿掉之后就不能再拿了。我们不妨看看重复背包问题的解法是不是能用到01背包上呢？还是讨论第一个拿的元素，设被拿掉的是第i个元素，问题就归结为把剩下的物品（注意，可拿的物品少了一件）最优地装入容量为 W-Wi 的包里，所以，问题的参数便变成了两个，一个是背包剩余容量 W-Wi，另一个是剩余可拿的物品集合 S\{i} （表示去掉i之后的子集），显而易见第二个参数是物品集合的各种可能的子集，那么其可能性个数就是 2^n ，这就导致子问题的个数是 2^n， 由于要依次计算每个子问题，那么算法复杂度显然也是 2^n ，是不可接受的。

那么，《Algorithms》上又是怎么来讲解01背包问题的解法的呢？以下是原文：

Our earlier subproblems now become completely useless. We must therefore refine our concept of a subproblem to carry additional information about the items being used. We add a second parameter, 0 <= j <= n: K(W, j) = maximum value achievable using a knapsack of capacity w and items 1..j: The answer we seek is K(W, n).

首先作者说了，之前重复背包问题的解法在这里完全废掉了，所以我们必须重新定义子问题，并且子问题的条件必须要包含目前拿剩下的物品。以上这些都还不错，关键是接下来就让人吐血了。作者接着说道，我们给子问题加上一个新的参数j…

凭什么啊？

还是让我们回顾一下这样一幅经典的漫画吧：

“我们给子问题加上一个参数j”，这就像你在看数学证明时看到无比邪恶的“我们考虑…“一样，一看到这样的句子，你就知道，这个问题的证明远远不像看上去那么简单，之所以你一路看下去理解上全无困难，那完全是因为作者直接把最重要的一个insight告诉你了，举个很简单的例子，证明素数无最大，谁都会第一时间想到去反证：假设存在一个最大的素数P，那么找到比P大的素数就是证明中最关键的一步，怎么找的？一般书上是不会说的，你会看到书上这样说：假设P是最大的素数，那么我们考虑P’ = 小于等于P的所有素数的乘积+1。那么P’一来显然大于P，二来不能被小于它的所有素数整除，那么P’就成了大于P的素数。

如果你经常注意反证法，你会发现一个有趣的现象，反证法里面经常会有这样一句“我们考虑”，而“我们考虑”后面几乎肯定接着一个天外飞仙一般的 insight。素数无最大这个古老的证明里面的“我们考虑”尚算是比较有迹可循的（我们想要构造一个更大的素数，而素数的等价定义就是“不能被小于它的所有素数整除，为了达到这个目的，构造的方法就较明显了）。但是有非常非常多的证明，其中关键的一步就跟做梦做出来走路跌跟头跌出来的一样（不信去翻一翻《Proofs from THE Book》），让你完全不知道他怎么想到的。

话说回来，虽然有很多数学证明的关键步骤是很难逆向工程的（因为很多时候想出那个关键步骤的本人其实也是尝试了各种方法，撞了无数堵墙，在寻求证法的尝试空间中作了N次回溯才“妙手偶得”，与其说是妙手偶得，不如说是绞尽脑汁），但并非全无章法可循，否则陶哲轩也不会写出《Solving Mathematical Problems》这样的著作来，而求解问题也就成了真正的Black Art了。

算法的解法则比精妙的数学证明稍加更容易逆向工程一点。只要你有耐心仔细地去琢磨算法的关键步骤和本质，总能从中窥探到一些更general的思想和思路来。

此外，很多经典问题，算法书上的讲法虽然时时令我们失望，但如果去网上一搜，则通常会发现更优秀的解释来。比如背包问题就是如此。

简单地说，如果你对于每个问题都能真正弄清以下这几个问题的答案，那么可以肯定的是，你的理解，记忆，以及学习的效率都会得到质的提高：

* 为什么这种解法是对的？
* 为什么那种解法是错的？
* 为什么这种解法不是最优的？
* 证明为什么没有更优的解法。

回到人民群众喜闻乐见的经典例子：背包问题。为什么01背包问题的正确（高效）算法是正确（高效）的。表面的解释是，因为01背包问题的子问题定义是 K(W, j)，其两个维度相乘的可能性一共有nW种，也就是说一共要计算nW个子问题，而计算每个子问题的复杂度是O(1)的。

但是如果仅仅满足于这样的解释，可以说是隔靴搔痒，并没有触及到本质。算法本质上可以看做是在一个解空间当中的搜索问题，所以要分析一个算法的好坏，首先弄清它的解空间的结构，然后分析它是怎么来探索这个解空间的。

弄清解空间的是第一步，例如排序算法，其解空间可以看做是所有可能的下标排列组合，其中有且仅有一个排列是正确的排序排列（简单起见假设元素各不相同）。那么一个算法在探索这个解空间方面的行为就决定了它的效率高低，最简单的，如果一个算法每次只能检查解空间中的一个点，那么这个算法的复杂度就是解空间的大小。对排序算法而言也就是n!。从这个角度来看，我们就会很容易的发现，所有基于比较的排序算法，其复杂度为什么是以O(nlogn)为下界的，因为一次比较操作最多有两个结果，a>b或a
回到01背包问题，01背包问题的解空间其实也是类似的。一次选取就是一个01数组，其中每个元素代表其所对应的物品要不要选取。很显然，这个解空间的大小是2^n。在01背包的算法里面，每当我们解出K(W, j)（需要O(W)次计算）之后，解空间就会被折半（排除掉1/2的可能性），一共如此做n次，就能得到最终解。由于每次折半的代价是O(W)，便不难理解为什么算法复杂度是O(nW)了。

那么，为什么每次计算出K(W,j)就能使解空间折半呢？那就需要来看看这个算法是如何探索解空间的，算法探索解空间的方式在其递归公式里面：

K(W, j) = max { K(W, j-1), K(W-Wj, j – 1) + Vj }

也就是说，首先看你要不要选取第一个物品，有两种可能性（两个分支），每个分支都是一个更低阶的子问题，即在其中的任意一个分支下都要决定要不要选取第二个物品（又是两个分支），如此下递归去，可以构建出一棵有2^n方个叶子节点的树，每条从根结点到叶子节点的路径“01..101”就对应一个解，其中每个分叉代表“选”或“不选”当前的物品。

建立在对这个解空间的理解上，我们再来看为什么01背包问题的正确解法能做到O(nW)。（首先你最好将这棵树画在纸上，其中每个节点都是一个子问题K(W,j)，每条分叉都是0或1。）当我们计算出所有的K(W, 1)（需要O(W)次操作）之后，我们容易注意到，所有离叶子节点的距离为1的内部节点K(W, 2)到叶子节点的两个分支都必然只能取其一了，也就是说，有一半的叶子节点被排除掉了（对解空间折半）。当我们进而计算出K(W,2)之后，同样的道理，我们容易看到，到叶子节点距离为2的内部节点的两个分支也只能取其一了，这就进而再次将解空间折半。由于每次折半需要O(W)的复杂度，所以就不难理解算法的总复杂度为O(nW)了。另一种理解的方法是，当我们计算出K(W,j)的时候，从内部节点K(W,j)到根节点的唯一路径便确定了。经过O(nW) 次计算，从根节点到那个唯一解（叶子节点）的路径便完全确定了。

知道怎么做是从正确（高效）解法得到的，而知道为什么必须得那样做则往往是从错误（低效）的解法当中得到的。

然而遗憾的是，绝大多数算法书或教程都只顾一上来就告诉你正确的做法是什么，对于一些常见的错误解法，或者常见的低效解法，却根本不加分析。经验告诉我们，理解错误的做法为什么错误同样甚至更为重要，往往是在理解了错误的解法为什么错误之后，我们才能深刻的体会到为什么正确的解法是如此正确。

还是拿经典的背包问题来作例子，你几乎看不到哪本书会告诉你一个典型的低效解法为什么低效的深刻原因。我们都知道动态规划的核心在于子问题的划分，同样的问题，不同的划分办法得到的复杂度完全不一样。前面已经提到了，重复背包问题的思路在01背包问题上会带来指数级的复杂度，但是为什么呢？如果你满足于说：因为如果拿重复背包问题的思路来解01背包问题，那么子问题定义的第二个维度（物品的子集）（见前文）是指数级的，那么要计算所有子问题，当然是指数级的。那么你只是看到这个问题的表象。

如果从对解空间的探索方式来说，可以容易看出这个现象的本质，我们回顾一下01背包问题的正确（高效）算法：

K(W, j) = max { K(W, j-1), K(W-Wj, j – 1) + Vj }

这个算法讨论的是两种情况，“要”或者“不要”选取第j个物品，这两种情况所对应的解空间是完全不交的，这就有效地将解空间划分为了不重复的两个部分。

而再来看利用重复背包问题思路的解法：

K(W, S) = max { K(W-Wi, S\{i}) + Vi : Wi <= W }

这里讨论的是首先拿掉哪一个物品，还是那句话，讨论的每一个分支都对应了算法对解空间的一个切分，我们容易看出，在“先拿物品i”和”先拿物品j “这两个分支里面，存在大量的重复，因为先拿物品i再拿j，和先拿物品j再拿i对应的是完全一样的一组选取。事实上，如果你将这个递归公式画成树状结构，会发现有n!个叶子节点。n!是什么概念？01背包问题的解空间大小本质上就只有2^n次方，穷举也不过O(2^n)的复杂度，结果这样一切分却变成了 n!，可见这种对解空间的切分方法的冗余度是多么高了。你不妨看看，每一次计算K(W, S)子问题能对解空间排查多少呢？是否能像前面正确的算法那样，每次都能有效排查一半情况？理解了这一点之后，我们便注意到在划分解空间，也就是定义子问题的时候的一个原则，就是在建立递归公式的时候，尽量将解空间进行不交的切分。同时我们便有了趁手的工具去分析一个动态规划的解法的效率。

最后再举一个例子：算法书上几乎必讲的霍夫曼树。你所看的算法书在讲霍夫曼树的时候给了证明吗？讲过霍夫曼树的历史八卦吗？也许你看了霍夫曼树的构造方法之后觉得：“哦，这样啊，显然”。但是你可曾想到，在最优编码这个问题上，连香农本人之前给出的解法都只是suboptimal的，而且霍夫曼本人在得到这个算法之前也是绞尽脑汁几近放弃。如果你10分钟就“理解”了，那么百分之百只是背了课文而已。