广大码农同学们大多都有个共识，认为算法是个硬骨头，很难啃，悲剧的是啃完了还未必有用——除了面试的时候。实际工程中一般都是用现成的模块，一般只需了解算法的目的和时空复杂度即可。

不过话说回来，面试的时候面算法，包括面项目中几乎不大可能用到的算法，其实并不能说是毫无道理的。算法往往是对学习和理解能力的一块试金石，难的都能掌握，往往容易的事情不在话下。志于高者得于中。反之则不成立。另一方面，虽说教科书算法大多数都是那些即便用到也是直接拿模块用的，但不幸的是，我们这群搬砖头的有时候还非得做些发明家的事情：要么是得把算法当白盒加以改进以满足手头的特定需求；要么干脆就是要发明轮子。所以，虽说面试的算法本身未必用得到，但熟悉各种算法的人通常更可能熟悉算法的思想，从而更可能具备这里说的两种能力。

那么，为什么说算法很难呢？这个问题只有两种可能的原因：

下面会说明，算法之所以被绝大多数人认为很难，以上两个原因兼具。

我们说算法难的时候，有两种情况：一种是学算法难。第二种是设计算法难。对于前者，大多数人（至少我当年如此）学习算法几乎是在背算法，就跟背菜谱似的（“Cookbook”是深受广大码农喜爱的一类书），然而算法和菜谱的区别在于，算法包含的细节复杂度是菜谱的无数倍，算法的问题描述千变万化，逻辑过程百转千回，往往看得人愁肠百结，而相较之下任何菜谱涉及到的基本元素也就那么些（所以程序员肯定都具有成为好厨师的潜力:D）注意，即便你看了算法的证明，某种程度上还是“背”（为什么这么说，后面会详述）。我自己遇到新算法基本是会看证明的，但是发现没多久还是会忘掉，这是死记硬背的标准症状。如果你也啃过算法书，我相信很大可能性你会有同感：为什么当时明明懂了，但没多久就忘掉了呢？为什么当时明明非常理解其证明，但没过多久想要自己去证明时却发现怎么都没法补上证明中缺失的一环呢？

初中学习几何证明的时候，你会不会傻到去背一个定理的证明？不会。你只会背结论。为什么？一方面，因为证明过程包含大量的细节。另一方面，证明的过程环环相扣，往往只需要注意其中关键的一两步，便能够自行推导出来。算法逻辑描述就好比定理，算法的证明的过程就好比定理的证明过程。但不幸的是，与数学里面大量简洁的基本结论不同，算法这个“结论”可不是那么好背的，许多时候，算法本身的逻辑就几乎包含了与其证明过程等同的信息量，甚至算法逻辑本身就是证明过程（随便翻开一本经典的算法书，看几个经典的教科书算法，你会发现算法逻辑和算法证明的联系有多紧密）。于是我们又回到刚才那个问题：你会去背数学证明么？既然没人会傻到去背整个证明，又为什么要生硬地去背算法呢？

那么，不背就不背，去理解算法的证明如何？理解了算法的证明过程，便更有可能记住算法的逻辑细节，理解记忆嘛。然而，仍然不幸的是，绝大多数算法书在这方面做的实在糟糕，证明倒是给全了，逻辑也倒是挺严谨的，可是似乎没有作者能真正还原算法发明者本身如何得到算法以及算法证明的思维过程，按理说，证明的过程应该反映了这个思维过程，但是在下文关于霍夫曼编码的例子中你会看到，其实饱受赞誉的CLRS和《Algorithms》不仅没能还原这个过程，反而掩盖了这个过程。

必须说明的是，没有哪位作者是故意这样做的，但任何人在讲解一个自己已经理解了的东西的时候，往往会无意识地对自己的讲解进行“线性化”，例如证明题，如果你回忆一下高中做平面几何证明题的经历，就会意识到，其实证明的过程是一个充满了试错，联想，反推，特例，修改问题条件，穷举等等一干“非线性”思维的，混乱不堪的过程，而并不像写在课本上那样——引理1，引理2，定理1，定理2，一口气直到最终结论。这样的证明过程也许容易理解，但绝对不容易记忆。过几天你就会忘记其中一个或几个引理，其中的一步或几步关键的手法，然后当你想要回过头来自己试着去证明的时候，就会发现卡在某个关键的地方，为什么会这样？因为证明当中并没有告诉你为什么作者当时会想到证明算法需要那么一个引理或手法，所以，虽说看完证明之后，对算法这个结论而言你是知其所以然了，但对于算法的证明过程你却还没知其所以然。在我们大脑的记忆系统当中，新的知识必须要和既有的知识建立联系，才容易被回忆起来（《如何有效地学习与记忆》），联系越多，越容易回忆，而一个天外飞仙似地引理，和我们既有的知识没有半毛钱联系，没娘的孩子没人疼，自然容易被遗忘。（为什么还原思维过程如此困难呢？我曾经在知其所以然（一）里详述）

正因为绝大多数算法书上悲剧的算法证明过程，很多人发现证明本身也不好记，于是宁可选择直接记结论。当年我在数学系，考试会考证明过程，但似乎计算机系的考试考算法证明过程就是荒谬的？作为“工程”性质的程序设计，似乎更注重使用和结果。但是如果是你需要在项目中自己设计一个算法呢？这种时候最起码需要做的就是证明算法的正确性吧。我们面试的时候往往都会遇到一些算法设计问题，我总是会让应聘者去证明算法的正确性，因为即便是一个“看上去”正确的算法，真正需要证明起来往往发现并不是那么容易。

所以说，绝大多数算法书在作为培养算法设计者的角度来说是失败的，比数学教育更失败。大多数人学完了初中平面几何都会做证明题（数学书不会要求你记住几何所有的定理），但很多人看完了一本算法书还是一团浆糊，不会证明一些起码的算法，我们背了一坨又一坨结论，非但这些结论许多根本用不上，就连用上的那些也不会证明。为什么会出现这样的差异？因为数学教育的理想目的是为了让你成为能够发现新定理的科学家，而码农系的算法教育的目的却更现实，是为了让你成为能够使用算法做事情的工程师。然而，事情真的如此简单么？如果真是这样的话干脆连算法结论都不要背了，只要知道算法做的是什么事情，时空复杂度各是多少即可。

如果说以上提到的算法难度（讲解和记忆的难度）属于Accidental Complexity的话，算法的另一个难处便是Essential Complexity了：算法设计。还是拿数学证明来类比（如果你看过《Introduction to Algorithms：A Creative Approach》就知道算法和数学证明是多么类似。），与单单只需证明相比，设计算法的难处在于，定理和证明都需要你去探索，尤其是前者——你需要去自行发现关键的那（几）个定理，跟证明已知结论相比（已经确定知道结论是正确的了，你只需要用逻辑来连接结论和条件），这件事情的复杂度往往又难上一个数量级。

一个有趣的事实是，算法的探索过程往往蕴含算法的证明过程，理想的算法书应该通过还原算法的探索过程，从而让读者不仅能够自行推导出证明过程，同时还能够具备探索新算法的能力。之所以这么说，皆因为我是个懒人，懒人总梦想学点东西能够实现以下两个目的：

想要做到这两点就必须尽量从知识树的“根节点”入手，虽然这是一个美梦，例如数学界寻找“根节点”的美梦由来已久（《跟波利亚学解题》的“一点历史”小节），但哥德尔一个证明就让美梦成了泡影（《永恒的金色对角线》））；但是，这并不阻止我们去寻找更高层的节点——更具普适性的解题原则和方法。所以，理想的算法书或者算法讲解应该是从最具一般性的思维法则开始，顺理成章地推导出算法，这个过程应该尽量还原一个”普通人“思考的过程，而不是让人看了之后觉得”这怎么可能想到呢？

以本文上篇提到的霍夫曼编码为例，第一遍看霍夫曼编码的时候是在本科，只看了算法描述，觉得挺直观的，过了两年，忘了，因为不知道为什么要把两个节点的频率加在一起看做单个节点——一件事情不知道“为什么”就会记不牢，知道了“为什么”的话便给这件事情提供了必然性。不知道“为什么”这件事情便可此可彼，我们的大脑对于可此可彼的事情经常会弄混，它更容易记住有理有据的事情（从信息论的角度来说，一件必然的事情概率为1，信息量为0，而一件可此可彼的事情信息量则是大于0的）。第二遍看是在工作之后，终于知道要看证明了，拿出著名的《Algorithms》来看，边看边点头，觉得讲得真好，一看就理解了为什么要那样来构造最优编码树。可是没多久，又给忘了！这次忘了倒不是忘了要把两个节点的频率加起来算一个，而是忘了为什么要这么做，因为当时没有弄清霍夫曼为什么能够想到为什么应该那样来构造最优编码树。结果只知其一不知其二。

必须说明的是，如果只关心算法的结论（即算法逻辑），那么理解算法的证明就够了，光背算法逻辑难记住，理解了证明会容易记忆得多。但如果也想不忘算法的证明，那么不仅要理解证明，还要理解证明背后的思维，也就是为什么背后的为什么。后者一般很难在书和资料上找到，唯有自己多加揣摩。为什么要费这个神？只要不会忘记结论不就结了吗？取决于你想做什么，如果你想真正弄清算法设计背后的思想，不去揣摩算法原作者是怎么想出来的是不行的。

回到霍夫曼编码问题，我们首先看一看《Algorithms》上是怎么讲的：

首先它给出了一棵编码树的cost function：

cost of tree = Σ freq(i) * depth(i)

这个cost function很直白，就是把编码的定义复述了一遍。但是接下来就说了：

There is another way to write this cost function that is very helpful. Although we are only given frequencies for the leaves, we can define the frequency of any internal node to be the sum of the frequencies of its descendant leaves; this is, after all, the number of times the internal node is visited during encoding or decoding…

接着就按照这个思路把cost function转换了一下：

The cost of a tree is the sum of the frequencies of all leaves and internal nodes, except the root.

然后就开始得出算法逻辑了：

The first formulation of the cost function tells us that the two symbols with the smallest frequencies must be at the bottom of the optimal tree, as children of the lowest internal node (this internal node has two children since the tree is full). Otherwise, swapping these two symbols with whatever is lowest in the tree would improve the encoding.

This suggests that we start constructing the tree greedily: find the two symbols with the smallest frequencies, say i and j, and make them children of a new node, which then has frequency fi + fj. To keep the notation simple, let’s just assume these are f1 and f2. By the second formulation of the cost function, any tree in which f1 and f2 are sibling-leaves has cost f1 + f2 plus the cost for a tree with n – 1 leaves of frequencies (f1 + f2), f3, f4, .., fn. The latter problem is just a smaller version of the one we started with.

读到这里我想大多数人有两种反应：

因为我当时也是这么觉得的。可是后来当我发现自己无法从头证明一遍的时候，我知道肯定是理解的不够深刻。如果理解的够深刻，那么基本上是不会忘掉的。

如果看完霍夫曼编码这样一个简短证明你觉得顺理成章，一切都挺显然，那就坏了，即便是看上去最基本的性质也往往实际上没那么显然。“逢山开路，遇水架桥”在我们今天看来是无比显然的事实，但是试想在没有桥的远古时代，一个原始人走到一条湍急的河流前，他会怎么想，他又能有什么法子呢？这是个他从来没有遇见过的问题。如果后来有一天，他路过另外一条小溪，看到小溪上有一截被闪电劈断的枯树，于是他踏着树干走过了小溪，并意识到“树横过河面”可以达到“过河”这个目的，这就将条件和目的建立了直接的联系（事实上，是自然界展示了这个联系，我们的原始人只是记住了这个联系）。后来他又路过那条河流，他寻思如何达到“过河”这个目的的时候，忽然意识到在他的记忆中已经遇到过需要达成同样目的的时候了，那个时候的条件是“树横过河面”，于是问题便归结为如何满足这个“树横过河面”的条件，而后一个问题就简单多了。（事实上波利亚在他的著作《How to Solve it》中举的正是这么个例子）

为什么那么多的算法书，就看不到有一本讲得好的？因为我们求解问题过程中的思维步骤太容易被自己当作“显然”的了，但除了我们天生就会的认知模式（联系，类比），没有什么是应该觉得显然的，试错是我们天生就会的思维法则么？是的，但是可供尝试的方案究竟又是怎么来的呢？就拿上面的例子来说，一个从没有见过枯树干架在小溪上的原始人，怎么知道用树架桥是一种可选的方案呢？俗话说巧妇难为无米之炊啊。我们大脑的神经系统会的是将目的和条件联系起来，第一次原始人遇到小溪过不去，大脑中留下了一个未实现的目的，后来见到小溪上的树干，忽然意识到树干是实现这个目的的条件，两者便联系起来了，因此问题就规约为如何架树干了。

回到《Algorithms》中的证明上，这个看似简洁明了的证明其实有几处非常不显然的地方，甚至不严谨的地方，这些地方也正是你过段时间之后试图自己证明的话会发现卡住的地方：

为什么要提到上面这几点不显然和不严谨的地方，因为只要当你看到算法书上出现不显然和不严谨的地方，基本上就意味着作者其实跳过了关键的思维步骤。

不幸的是《Algorithms》这本书里面讲霍夫曼编码已经算是讲的好的了，如果你翻开著名的CLRS，看一看当中是怎么证明的，你就知道我说的什么意思了。有时候这些证明是如此的企图追求formal和严谨，一上来就定义符号一大摞，让人看了就想吐。

说了这么多，有没有可能把霍夫曼编码讲的更好呢？前面说过，霍夫曼编码我记了又忘，忘了又记，好几次了，有一次终于烦了，心想如果要自己去证明，会怎么去证，那个时候我已经忘了《Algorithms》里面怎么讲的了。所以我得从头来起，首先，对于算法问题，有一个一般性原则是，先看一看解空间的构成。尤其是对于搜索问题（最优化问题可以看做搜索问题的一个特例），这一点尤其重要。霍夫曼编码的可能的编码树是有穷的，如果穷举所有的编码树，然后找到那棵代价最小的，这种方法至少是可行的，有了可行的方法（即便是穷举）至少让我们内心感到踏实。

接下来便是提高搜寻效率的问题。而提高搜寻效率的关键（同样也是一个一般性原则），便是尽量去寻找问题条件能够推导出来的性质，然后利用这些性质去避免不必要的搜寻，只要你学过二分搜索就应该理解这个一般性原则：二分搜索的效率之所以高于“穷搜”（O(n)），便是因为它利用了问题中的性质（有序）来避免了不必要的搜寻。有时候这个性质甚至可以直接将时间降为O(1)，例如在一个有序数组中寻找出现次数大于n/2的数（假设该数存在），利用“该数一定出现在数组正中间”这个性质，我们直接就避免了所有的计算。

不过，话虽如此，有时候这些性质并不是那么“显然”的，需要对问题进行深入的折腾才能有可能发现。第三个一般原则：如果你要搜寻的元素是某个满足特定条件的元素（例如寻找最优解的时候，“最优”的定义就是这个“特定条件”），那么可以“倒过来推”（数学证明常用手法，结论当条件使），即假设你已经找到了你要找的元素，那么能得出哪些结论，每一个结论都是最优解的一个必要条件，而每一个必要条件都能够帮助你避免不必要的搜寻，因为你只要发现某个候选解不满足某个必要条件，就可以立即将其丢弃，前面提到的寻找出现次数大于n/2的例子是一个极端情况，我们得出的必要条件导致我们可以直接丢弃除中点元素之外的一切其他元素，再例如如果有人叫你寻找有序数组中最小元素，你会毫不犹豫地把该数组头尾元素中较小的那个给他，因为你知道“如果那个最小元素存在，那么它必然位于头尾”——这个必要条件直接允许你丢弃掉n-2个候选解。

回到霍夫曼编码问题，按照这个原则，我们会去假设已经得到了最优编码树，那么我们能够发现关于它的什么性质呢？这里又要提到另一个适用于很多最优化问题的原则（前面提到的原则适用于一般性搜索问题），所谓最优解，就是说比其他所有解都要更好，虽然这句话听上去像是废话，但是它的一个直接推论——比与它邻近的所有候选解都要好——就是一个非常有用的，不是废话的性质了。学过微积分的都知道，光滑函数的最值点必然是大（小）于其邻域内的所有点的，然后再根据这个就自然推出该点的一阶导数（切线斜率）必然为0的性质，这个性质（必要条件）让我们直接省掉了去整个区间内搜索的麻烦，从而可以直接锁定有限几个候选解。那么，既然我们说最优霍夫曼树一定比它“附近”的树更好，我们就想看看，怎么来找到它附近的树。我们知道要从一个点到它附近，往往是对这个点进行一些调整，例如N+1是到达附近的另一个整数。霍夫曼树是一棵树，所以对这棵树的所有的一次“改动”（或“折腾”）都能够到达与它的“改动”距离为1的点（是不是想起“编辑距离”这个概念），怎么改动呢？最符合直觉的（虽然并不是唯一的）改动便是把叶子节点进行互换。

于是我们得到一个重要的推论：

这个性质看上去有点像废话，值得费这么多事么？值得。因为虽然前文说了很多，但都是大多数人大脑里面既有的，一般性的法则，前面说过，如果我们能够从我们已经掌握的一般法则出发来推导出问题的解，那么记忆负担是最小的，因为这里面用到的所有法则我们都很清楚，也知道怎么一步步往下走。

上面这个性质究竟意味着什么呢？如果你假设这两个叶子节点的频率为f1和f2，深度为d1和d2，互换它们的时候，其他叶子节点的cost保持不变，令为常量C，那么互换前总cost为C+f1d1+f2d2，互换后为C+f1d2+f2d1，既然互换之后的树一定更”差“那么就是说f1d1+f2d2 < f1d2 + f2d1，简单变换一下就得到结论：f1(d1-d2)d2，那么f1必然