恢弘码农同窗们除夜多都有个共叫，认为算法是个硬骨头，很难啃，悲剧的是啃完了还未必有效——除面试的时辰。理论工程中一样往常都是用现成的模块，一样往常只需体味算法的方针和时空宏壮度便可。

不过话说归来，面试的时辰面算法，包含面项目中几近不除夜大年夜大年夜约用到的算法，真实真实不克不及说是毫无事理的。算法经常是对进修和邃晓身手的一块试金石，难的都能掌控，经常随便的工作不在话下。志于高者得于中。反之则不创建。此外一方面，当然说教科书算法除夜除夜都都是那些即应用到也是直接拿模块用的，但不幸的是，我们这群搬砖头的有时光还非得做些创作创造家的工作：要么是得把算法当白盒加以改进以知足手头的特定需求；要么干脆就是要创作创造轮子。所以，当然说面试的算法本身未必用掉落踪掉落踪，但熟谙各类算法的人但凡更大年夜大年夜约熟谙算法的思惟，从而更大年夜大年夜约具有这里说的两种身手。

那么，为甚么说算法很难呢？这个问题只需两种大年夜大年夜约的启事：

算法本身就很难。也就是说，算法这个对象对人类的除夜脑来讲本身就是个艰苦的事儿。讲得太烂。

上面会声明，算法之所以被尽除夜除夜都人认为很难，以上两个启事兼具。

我们说算法难的时辰，有两种气候：一种是学算法难。第二种是设筹算法难。对前者，除夜除夜都人（起码我昔时如斯）进修算法几近是在背算法，就跟背菜谱似的（“Cookbook”是深受恢弘码农快活喜悦爱好的一类书），可是算法和菜谱的分辨在于，算法包含的细节宏壮度是菜谱的罕有倍，算法的问题描摹变换无常，逻辑过程百转千回，经常看得人满腹忧虑，而相较之下任何菜谱触及到的根本元素也就那么些（所以法度圭表类型员必定都具有成为好厨师的潜力:D）寄看，即便你看了算法的证实，某种程度上仍是“背”（为甚么这么说，后背会胪陈）。我本身碰着新算法根本是会看证实的，可是创作创造没多久仍是会忘损掉落踪落，这是融合贯穿的标准症状。假定你也啃过算法书，我信赖很除夜大年夜大年夜约性你会有同感：为甚么事前光鲜较着懂了，但没多久就忘损掉落踪落了呢？为甚么事前光鲜较着十了了白其证实，但没过量久想要本身往证实时却创作创造若何都没法补上证实中缺损掉落踪落的一环呢？

初中进修若干很多若干证实的时辰，你会不会傻到往背一个定理的证实？不会。你只会背结论。为甚么？一方面，因为证实过程包含除夜量的细节。此外一方面，证实的过程环环相扣，经常只需求寄看个中关头的一两步，便可以自行推导出来。算法逻辑描摹就比如定理，算法的证实的过程就比如定理的证实过程。但不幸的是，与数学里面除夜量精练的根本结论不合，算法这个“结论”可不是那么好背的，良多时辰，算法本身的逻辑就几近包含了与其证实过程齐截的信息量，甚至算法逻辑本身就是证实过程（尽情翻开一本经典的算法书，看几个经典的教科书算法，你会创作创造算法逻辑和算法证实的联络有多严密）。是以我们又回到刚才阿谁问题：你会往背数学证实么？既然没人会傻到往背全数证实，又为甚么要僵硬地往背算法呢？

那么，不背就不背，往邃晓算法的证实若何？邃晓了算法的证实过程，便更有大年夜大年夜约记住算法的逻辑细节，邃晓记忆嘛。可是，还是不幸的是，尽除夜除夜都算法书在这方面做的真实糟，证实倒是给全了，逻辑也倒是挺严谨的，可是似乎没有作者能真正恢复算法创作创造者本身若何掉落踪掉落踪算法和算法证实的思惟过程，按理说，证实的过程理应回响了这个思惟过程，可是不才文关于霍夫曼编码的例子中你会看到，真实饱受赞誉的CLRS和《Algorithms》不单没能恢复这个过程，反而点缀了这个过程。

必须声明的是，没有哪位作者是专心多么做的，但任何人在解释注解一个本身已邃晓了的对象的时辰，经常会有时识地对本身的解释注解举办“线性化”，比如证实题，假定你回想一下高中做立体若干很多若干证实题的经验，就会熟悉到，真实证实的过程是一个布满了试错，联想，反推，特例，改削题今朝提，穷举等等一干“非线性”思惟的，混乱不堪的过程，而真实不像写在教材上那样——引理1，引理2，定理1，定理2，一口气直到幻想下场结论。多么的证实过程大年夜大年夜约随便邃晓，但尽对不随便记忆。过几天你就会遗忘个中一个或几个引理，个中的一步或几步关头的手段，然后当你想要回过分来本身试着往证实的时辰，就会创作创造卡在某个关头的中心，为甚么会多么？因为证实傍边并没有陈述你为甚么作者事前会想到证实算法需求那么一个引理或手段，所以，当然说看完证实此后，对算法这个结论而言你是知其所以然了，但对算法的证实过程你却还没知其所以然。在我们除夜脑的记忆琐细傍边，新的常识必须乞降既有的常识创建联络，才随便被回想起来（《若何有效地进修与记忆》），联络越多，越随便回想，而一个天外飞仙似地引理，和我们既有的常识没有半毛钱联络，没娘的孩子没人疼，天然随便被遗忘。

正因为尽除夜除夜都算法书上悲剧的算法证实过程，良多人创作创造证实本身也不好记，是以宁愿选择直接记结论。昔时我在数学系，考验会考据明过程，但似乎筹算机系的考验考算法证实过程就是荒诞的？作为“工程”性质的法度圭表类型筹划，似乎更留心独霸和下场。可是假定是你需求在项目中本身计整洁个算法呢？这类时辰最起码需求做的就是证实算法的切确性吧。我们面试的时辰经常都邑碰着一些算法筹划问题，我老是会让应聘者往证实算法的切确性，因为即就是一个“看上往”切确的算法，真正需求证实起交经常创作创造真实不是那么随便。

所以说，尽除夜除夜都算法书在作为培养算法筹划者的角度来讲是损掉落踪落败的，比数学经历更损掉落踪落败。除夜除夜都人学完了初中立体若干很多若干都邑做证实题（数学书不会请求你记住若干很多若干全数的定理），但良多人看完了一本算法书仍是一团浆糊，不会证实一些起码的算法，我们背了一坨又一坨结论，不单这些结论良多根柢用不上，就连用上的那些也不会证实。为甚么会展示多么的不合？因为数学经历的志向方针是为了让你成为可以创作创造新定理的科学家，而码农系的算法经历的方针却更理论，是为了让你成为可以独霸算法干工作的工程师。可是，工作真的如斯复杂么？假定真是多么的话干脆连算法结论都不要背了，只需晓得算法做的是甚么工作，时空宏壮度各是若干很多若干良多若干很多若干良多若干很多若干便可。

假定说以上提到的算法难度（解释注解和记忆的难度）属于Accidental Complexity的话，算法的此外一个难处等于Essential Complexity了：算法筹划。仍是拿数学证实来类比（假定你看过《Introduction to Algorithms：A Creative Approach》就晓得算法和数学证实是多么近似。），与单单只需证实比照，设筹算法的难处在于，定理和证实都需求你往试探，不凡是前者——你需求往自行创作创造关头的那（几）个定理，跟证实已知结论比照（已断定晓得结论是切确的了，你只需求用逻辑来邻接结论和前提），这件工作的宏壮度经常又难上一个数量级。

一个滑稽的理论是，算法的试探过程经常包含算法的证实过程，志向的算法书理应经由过程恢复算法的试探过程，从而让读者不单可以自行推导出证实过程，同时还可以具有试探新算法的身手。之所以这么说，皆因为我是个懒人，懒人总胡想学点对象可以完成以下两个方针：

进步神速：法度圭表类型员都晓得“一次编写四处运转”的益处，多省事啊。学了就忘，忘了又得学，翻来覆往华侈生命。为甚么不克不及看了一遍就不再会忘损掉落踪落呢？幻想下场是教的不好，仍是学得不好？事半功倍：理论上，法度圭表类型员不单讲究一次编写四处运转，更讲究“一次编写四处独霸”（也就是俗称的“复用”）。假定学一个算法所掉落踪掉落踪的经验可以四处独霸，学一当十，推而广之，时分的独霸屈就便会除夜除夜进步。幻想下场若何进修，才调够使得经验的外推（extrapolate）屈就抵达最除夜呢？

想要做到这两点就必须尽大年夜大年夜约从常识树的“根节点”进手，当然这是一个好梦，比如数学界寻觅“根节点”的好梦由来已久（《跟波利亚学解题》的“一点汗青”大年夜节），但哥德尔一个证实就让好梦成了泡影（《永远的金色对角线》））；可是，这真实不由止我们往寻觅更高层的节点——更具普适性的解题绳尺和编制。所以，志向的算法书或算法解释注解理应是从最具一样往常性的思惟律例最早，瓜熟蒂落地推导出算法，这个过程理应尽大年夜大年夜约恢复一个”深化人“思虑的过程，而不是让人看了此后感应感染”这若何大年夜大年夜约想到呢？

以本文上篇提到的霍夫曼编码为例，第一遍看霍夫曼编码的时辰是在本科，只看了算法描摹，感应感染挺直不美不雅不雅不雅不雅不雅不雅的，过了两年，忘了，因为不晓得为甚么要把两个节点的频率加在一同看作单个节点——一件工作不晓得“为甚么”就会记不牢，晓得了“为甚么”的话便给这件工作供给了有时性。不晓得“为甚么”这件工作便可此可彼，我们的除夜脑对可此可彼的工作经常会弄混，它更随便记住有理有据的工作（从信息论的角度来讲，一件必定的工作概率为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 ++allest 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 ++allest frequencies, say i and j, and make them children of a new node, which then has frequency fi + fj. To keep the notation ***, 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 ++aller version of the one we started with.

读到这里我想除夜除夜都人有两种回响：

感应感染不移至理。感应感染恍然除夜悟。

因为我事前也是这么感应感染的。可是后来当我创作创造本身没法从头证实一遍的时辰，我晓得必定是邃晓的不足深切。假定邃晓的够深切，那么根本上是不会忘损掉落踪落的。

假定看完霍夫曼编码多么一个冗长证实你感应感染瓜熟蒂落，实足都挺较着，那就坏了，即就是看上往最根本的性质也经常理论上没那么较着。“逢山开路，遇水架桥”在我们往日看来黑色常较着的理论，可是试想在没有桥的泰初时代，一个原始人走到一条湍急的河道前，他会若何想，他又能有甚么编制呢？这是个他历来没有碰见过的问题。假定后来有一天，他路过此外一条小溪，看到小溪上有一截被闪电劈断的枯树，是以他踏着树干走过了小溪，并意想到“树横过河面”可以抵达“过河”这个方针，这就将前提和方针创建了直接的联络（理论上，是天然界展示了这个联络，我们的原始人只是记住了这个联络）。后来他又路过那条河道，他沉思若何抵达“过河”这个方针的时辰，俄然意想到在他的记忆中已碰着过需哀杀青一样方针的时辰了，阿谁时辰的前提是“树横过河面”，是以问题便回结为若何知足这个“树横过河面”的前提，此后一个问题就复杂多了。（理论上波利亚在他的著作《How to Solve it》落第的恰是这么个例子）

为甚么那么多的算法书，就看不到有一本讲得好的？因为我们求解问题过程中的思惟法度圭表类型太随便被本身算作“较着”的了，但除我们见成效会的认知编制（联络，类比），没有甚么是理应感应感染较着的，试错是我们见成效会的思惟律例么？是的，可是可供考验考验的筹划幻想下场又是若何来的呢？就拿上面的例子来讲，一个从没有见过枯树干架在小溪上的原始人，若何晓得用树架桥是一种可选的筹划呢？鄙谚说巧妇难为无米之炊啊。我们除夜脑的神经琐细会的是将方针和前提联络起来，第一次原始人碰着小溪过不往，除夜脑中留下了一个未完成的方针，后来见到小溪上的树干，俄然意想到树干是完成这个方针的前提，二者便联络起来了，是以问题就规约为若何架树干了。

回到《Algorithms》中的证实上，这个看似精练了然的证实真实有几处特别很是不较着的中心，甚至不严谨的中心，这些中心也恰是你过段时分此后试图本身证实的话会创作创造卡住的中心：

作者轻飘飘地就给出了cost function的此外一种关头的描摹，而对若何创作创造这类描摹却只是一语带过："There is another way to write this cost function that is very helpful.. we can define the frequency of any internal node to be the sum of the frequencies of its descendant leaves“这真实就是我经常懊悔的“我们思虑…”，这里作者真实就是在说”让我们思虑上面多么一种奇妙的转换“，可是若何来的却不说。但必须招认，《Algorithms》的作者仍是算忠诚的，因为后背他又略微诠释了一下：“this is, after all, the number of times the internal node is visited during encoding or decoding…”这个诠释就有点让人恍然除夜悟了，可是切切别忘了，这类恍然除夜悟是一种错觉，你仍是没除夜白为甚么他会想到这一点。这就像是作者对你说“细心不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅查询拜访题今朝提，我们随便创作创造多么一种奇妙的性质..”，若何个“细心”法？凭甚么我本身“不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅查询拜访”半天就是创作创造不了呢？霍夫曼本身莫非也是作古作古盯着问题“不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅查询拜访”了一学期然后就“创作创造”了么？我们有出处信赖霍夫曼必定考验考验了各类各式的编制，作出了各类各式的戮力，不然昔时Shannon都没弄定的这个问题花了他一学期，莫非他在这个学期里面除夜脑就一片空白（或全数的考验考验全都是无缺不相干的白费），然后到学期开首俄然“灵光一现”吗？假定“细心不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅查询拜访”:)，我们会创作创造两个cost function表达中frequency的定见有奇妙的不合，在第一个cost function中，只需叶子节点有frequency，而这个frequency必须和叶子节点的深度相乘。而在第二个cost function中，内部节点也具有了frequency，可是全数节点的“frequency”俄然全都不跟深度相乘了。frequency的不合含义令人思疑。作者提到：第一个cost function陈述我们频率最低的两个节点必定处于最优编码树的底端，作为最低内部节点的两个子节点。这是一个不严谨的说法，畴前文给出的前提和性质，只能推导出编码树的最底层必定能找到频率最低的两个节点，但它们未必必定假定兄弟节点，假定树的最底层不止能包涵两个节点的话它们便可以有不合的父节点。“我们不妨思虑”多么一个例子：对A,B,C,D四个字母举办编码，假定它们的频率分袂是1， 1， 2， 2。这个时辰我们可以构造以下图所示的两棵树，两棵树的cost都是12，都是最优的。但个中一棵树中，两个频率最低的节点并不是兄弟。

为甚么要提到上面这几点不较着和不严谨的中心，因为只需当你看到算法书上展示不较着和不严谨的中心，根本上就意味着作者真实跳过了关头的思惟法度圭表类型。

不幸的是《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)<f2(d1-d2)，也就是说假定d1<d2，那么f1必定>f2，假定d1>d2，那么f1必定<f2。换言之就是叶子节点的深度越高，频率必须越低，不然就不成能是最优霍夫曼树。那么，之前我们感应感染不那么较着的结论便呼之欲出了：频率最低的叶子节点必定位于树的最底层，频率最高的叶子节点必定位于树的最高层。

有了这个结论此后，我们便可以对最优霍夫曼树的构建走出断定性的一步，即，将频率最低的两个叶子节点放在最底层。别嫌弃这一步，这一步已消弭除夜量的大年夜大年夜约性。这里，我们随便一最早无邪地感应感染最底层只需这两个叶子节点，是以它们具有合营父节点，多么一来霍夫曼树的全数拼图便已拼好了一个小小的角落。

然后我们会创作创造，假定它们不是兄弟若何办呢？这里提到此外一个一样往常绳尺——回约。不是兄弟的气候可否回约为是兄弟的气候？回正我们请求的是一个最优解，而不是全数的最优解，我们只需证实，假定当这两个最低频率的叶子不是兄弟的时辰切实其实存在着某棵最优霍夫曼树，那么经由过程交换它们各自的兄弟，从而让这两个叶子聚会此后，改削后的树还是是最优的便可以了。理论气候也切实其实如斯，证实特别很是直接——既然这里触及到的全数4个节点都在最底层不合个高度上，那么互订交换的时辰不会改削他们任何一小我的深度值，所以总cost不会改削。

可是接上往我们犯了难，全数树的一个小小的樱桃状的部分是断定上往了，接上往若何办呢？一个最天然的思路就是思虑第三小的叶子，因为后面说了，元素频率越高攀越位于树的底部嘛。第三小的叶子有两种大年夜大年夜约的回属，一是跟最小的两个叶子一样位于最底层（这不会背反我们后面掉落踪掉落踪的推论），这个时辰第三小的叶子的兄弟叶子必定是第四小的叶子，以下图：

此外一种回属就是往上一层往（寄看，一旦第三小的叶子往上往了一层，那么剩下的全数叶子都必须起码在这个层以上），往上一层往了此后，它的兄弟是谁呢？不妨将它和刚才第一第二叶子的父节点结为兄弟（后面证实过，同层之前节点交换不会改削编码的cost），以下图：

可是如今问题展示了：当然第一步构建（最小的两个叶子）是断定的，可是到了第二步摆在我们面前的就有两个选择了，幻想下场选择哪个呢？逐浅近例就是把两种选择都记上往，然后延续往下走。可是别嫌弃两种选择，接下往每步都有两种选择的话就变成指数宏壮度了。所以如今我们便有了念头回头看一看，看问题中可否有甚么没有创作创造的性质可以辅佐我们再消弭损掉落踪落个中一个选择。志向气候下假定每步都是必定的，断定的，那么N步我们便可以构建出整棵树，这是我们希看看到的，抱着这个出色的欲看，我们细心不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅查询拜访上面两种构型，一个自可是然的问题是：这两种构型都有潜质成为最优解吗？假定我们可以证实个中一种构型不克不及成为最优解那该多好？就省事多了嘛。这里引进此外一个一样往常性的解题律例：特例。我们的除夜脑快活喜悦爱好具体的对象，在特例中折腾和不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅不雅查询拜访会利便的多。

上面这个{1, 2, 3, 4}的例子就是个很好的特例，如图（注：图中节点旁的数字一概为频率值，而非编号）：

多加折腾一番大年夜大年夜约我们不难创作创造，假定将1，2及其父节点跟叶子4举办交换（寄看：交换的时辰1，2也被一同带走了，因为回正1，2两个节点已断定是好兄弟永远不会分炊了，折腾的时辰只能作为一个集团挪动，所以这里也可以说是交换子树），那么树的编码将会变得更优，因为多么一次交换会将1和2的深度+1，意味着整棵树的价值+3，而同时会将叶子4的深度-1，也就是说整棵树的价值-4，集团上整棵树的价值就是+3-4=-1（寄看，在筹算的时辰我们只需思虑被交换的部分，因为树的其他部分的价值贯穿连接晃荡）。以下图：

这个交换启发了我们，真实后面一最早说的交换两个叶子节点可以推荐动交换内部节点和叶子节点，然后很快我们就会熟悉到真实可以奉行到交换肆意两个节点。（寄看，当我们说交换内部节点的时辰，理论上是连同该内部节点作为部分根节点的全数子树都交换畴昔）是当前面我们的推论便可以推荐动：

在最优霍夫曼树中，非论交换哪两个节点，掉落踪掉落踪的树都变得更“差”（交换内部节点则是连同该内部节点作为部分根的子树一同带走）

这个推论很随便邃晓，只不过是多添加了一种“编辑”最优霍夫曼树的编制罢了（记住最优霍夫曼树非论若何“编辑”都不会变得更“好”，包含“交换子树”这类“编辑”），我们后面没有想到这类“编辑”编制是因为它不那么较着，并且事前我们已想到一种最直接的“编辑”编制了，即交换叶子，就随便顺着阿谁思路不时走下往，直到我们创作创造必须寻觅新的性质，才回过分来看看有没有其他编制。

当然，真实不必弭一最早就想到这类奉行的大年夜大年夜约性，问题求解的过程真实不是这么线性的，假定我们习惯了推而广之的思惟，大年夜大年夜约一下就可以想到这个奉行来。近似的，也不必弭从此外一种思路解缆想到这类奉行的大年夜大年夜约性。所以这里只是大年夜大年夜约的思惟轨迹中的一种，重点在于个中并没有某处俄然展示一个不知从何处冒出来的，神启一样往常的结论。

刚才提到，构造最优树的第二步是思虑第三小的叶子，但也有此外一种罕有的思惟：思虑到第一步（即拔取频率最小的两个叶子）所做的工作是从N个叶子被选择两个黏在一同作为兄弟，那么大年夜大年夜约对一些人来讲自可是然的第二步就是试图延续拔取两个节点黏在一同作为兄弟（寄看这里不单可以选择叶子，也可以选择已生成的内部节点），然后按序类推来拼无缺棵树。屈就这一思路，第二步的选项还是仍是集结在第三小的叶子上，因为这个选摘要么是让第三第四小的叶子结拜为兄弟，要么是让最小两个叶子的父节点和第三小的叶子结拜。

回到刚才我们的推论：在最优霍夫曼树中，非论交换哪两个节点，掉落踪掉落踪的树都变得更“差”（交换内部节点则是连同该内部节点作为部分根的子树一同带走） 。屈就这个推论我们随便筹算出，在最优霍夫曼树傍边，两个内部节点n1和n2，假定n1比n2更深，那么n1上面的全数叶子的频率之和必定要小于n2上面全数叶子的频率之和。假定交换的是一个内部节点和一个叶子节点，则事理是近似的。这赋性质的证实和上面的近似，就不赘述了。

这赋性质展示了一个次要的奉行结论：假定我们把每个内部节点的全数叶子的频率之和标在它旁边，那么整棵树的每个节点便都有了一个数值，这个数值屈就不合的规律：即越往深层越小。这就意味着，我们刚才的二选一困境有编制了！当我们将最小的两个叶子f1和f2回并的时辰，生成了一个新的节点M，这个节点有一个数字（为两个叶子的频率之和f1+f2），屈就上面的推论，这个数字f1+f2跟全数频率一同，屈就最小的在最底层的绳尺，所以我们下一步必须在剩下的那些彼此之间相干待断定的节点（叶子节点和内部节点）傍边，即{(f1 + f2), f3, f4}里面选择最小的两个数字结分化兄弟（因为f1和f2这两个节点已铁板钉钉结为集团了，所以从集结里面可以看作移除）。到这里，我们就创作创造递回已展示了，接下往的过程对尽除夜除夜都人理应就真的很较着了。

以上的诠释，比《Algorithms》更冗长吗？较着不是。反而要长良多（真实真实的思惟过程比这要更长，因为中心还会触及各类不成功的考验考验）。可是它比《Algorithms》傍边的版本更不随便被遗忘，因为个中关头的思惟拐点真实不是毫无出处的，而是从你已熟知的，或说当然不晓得，但随便邃晓的一样往常性解题律例解缆天然推导出来的，所以你根本上不须要记忆甚么对象，因为你需求记的已在你脑海中了。

不才面的证实过程中，另有一个不像看上往那么较着的工作：在我们寻觅最优霍夫曼树的时辰，我们曾试图往斗劲想象的最优树和它的“邻近”的树，从而往试探最优树的性质。可是，幻想下场甚么是邻近的树？在后面的解释注解中，我们说假定交换A和B这两个叶子节点，便掉落踪掉落踪一颗不合的树，可以看作和原树的“编辑距离”为1的树。可是，真的这么较着么？莫非除交换叶子的职位，就没有其他编制往“折腾”这棵树了？后来我们看到，可以交换子树而不单仅是叶子，而交换子树让我们掉落踪掉落踪了相当次要的推论。此外，假定不是交换，而是像AVL树那样“改削”呢？说幻想下场，二叉树是一个聚会的对象，真实不像延续值那样，见成效有“距离”这个定见，假定我们聚会而孤当即往对待全数的树，那么没有甚么邻近不邻近的，邻近本是一个距离的定见，除非我们定义树和树之间的距离函数，才调说邻近与否，而距离函数若何定义才是“较着”的呢？

另有，真实以上只是试图给出最优霍夫曼树的证实的一个更天然的过程，而昔时霍夫曼面对这个问题标时辰根柢还没有人想到要用二叉树呢！更不要说在二叉树的前提之下举办证了然。屈就+++++++++的引见，霍夫曼同窗（昔时还在读Ph.D，所以切实其实是“同窗”，而这个问题是坑爹的导师Robert M. Fano给他们作为高文业的，Fano本身和Shannon合作给出了一个suboptimal的编码筹划，为得不到optimal的筹划而寝食难安，情急之下便作古马当活马医扔给他的师长教师们了）昔时为这个问题蕉萃了一个学期，末尾就快到deadline的时辰“俄然”想到二叉树这个等价模型，然后在这个模型下三下五除二就弄定了一篇流芳千古的论文，超出了其导师。

末尾说两个滑稽的气候：大年夜大年夜约良多人会感应感染，越是大年夜师来写进门教科书越是好，真实良多时辰并不是如斯，不凡是在算法筹划和数学局限，经常越是在个中浸***久了越是难写出切近初学者的书，因为除夜量对初学者来讲一点都不较着的工作在他看来已经是“不假思虑”了，成了他的内隐记忆，不凡是当他想要和你诠释一个宏壮的对象的时辰你就会创作创造他会经常逻辑腾踊，满嘴跑术语，根柢没居心想到别人对有些术语和隐含的逻辑根柢没有像他那样的邃晓。

最契合将一个对象讲给别人听的时辰真实不是等懂了良多年往后，而是刚才弄懂的时辰，这个时辰从不懂到懂的不合记忆还特别很是光鲜，可以幽暗了楚地记掉落踪掉落踪底是哪些关头的中心是最熬煎人的，也最可以站在不懂者的角度来思虑问题。像波利亚多么，成了大年夜师还可以站在不懂者角度往换位思虑的，可以说是凤毛麟角。所以说前Amazon CAO（首席算法官）的《Introduction to Algorithms: a Creative Approach》尽对是本罕有的好算法书）

知其所以然（一）里面曾提到，要弄清来龙往脉，最好往看看原始作者是若何想的，可是正如上文所说，即就是最初的创作创造者，在陈述的时辰也会居心有时地“线性化”，我就往搜检了霍夫曼最初的论文，那叫一个隐晦，不信你可以本身看看(PDF)。

可以回约为搜刮算法的问题（特别很是多）一样往常来讲绝对仍是有一些端倪的，因为搜刮空间一样往常还斗劲随便界定，难点在于要从问题标前提中推导出用于俭仆搜刮的性质。而计策筹划问题则美尽是此外一个全国，因为计策的筹划空间貌似是可列无量的，经常让人感应感染无从进手，摸不着端倪，良多让人挠头的智力问题就有这个特点（例如有名的100个阶下囚和1个灯胆的房间就让良多人有这类感应感染），计策筹划问题也有一些较通用的律例，往后再说。

若何才调在学算法的时辰学到面前的对象呢？有以下几点很次要：

不要感应感染每个法度圭表类型都很较着，每个nontrivial的算高面前都有一段艰苦的试探经验，感应感染较着的话必定是一种幻觉。Stay foolish，才调创作创造某些环节真实真实不是那么较着的考验可否真正邃晓的最好编制就是过一段时分此后，本身试着证实一次。假定真正邃晓了的话，你的证实便会斗劲顺畅。假定事前没有真正邃晓，那么但凡那些你事前感应感染较着但真实不较着的中心，都邑成为你证实里面缺损掉落踪落的环节。对一个算法，多寻觅各类本源的材料，或承诺以大年夜大年夜约找到一个讲的斗劲深切的。我在《数学之美番外篇：快排为甚么那么快》和《知其所以然（一）》里面都举到了多么的例子。多试着往笼统面前的一样往常性律例，即便后来创作创造笼统得是错的，也比不往笼统要好。笼统是奉行的根本。只需笼统出更深层的律例，才调让你事半功倍，触类旁通，不然一个萝卜永远是一个坑。（寄看，真实我们的下见识是会举办必定程度的笼统的，比如后面提到的原始人的例子，小溪和小河（或小沟）细节上是不合的，但本质上是一样的，我们的除夜脑会主动举办这类复杂笼统，提丧出事物的特点。恰是以，即便你不往居心识地总结一样往惯例律，只需你看的充分多，练的充分多，必定就会愈来愈谙熟。）

末尾留个问题：当然屈就上文的编制来构造霍夫曼树必定可以掉落踪掉落踪一个最优树，可是若何证实必定能掉落踪掉落踪呢？乍一看这个问题似乎很多余，因为证实很复杂：我们拼装整棵树的每步都没得选，并且每步都必定凑合出最优树的一个小小部分，假定幻想下场还没有掉落踪掉落踪最优树的话，只能说最优树是不存在的了，可是最优树是必定存在的，因为全数树的集结是有穷的，有穷集必有最值，是以证毕。这个证实当然是没问题标，但它理论上是一个直接证实，换句话说，我们在构成立的过程中的逻辑是多么的：“之所以我们选择粘结n1和n2，是因为其他粘法必定背反最优树的两赋性质。所以我们别无选择。”可是，这并没有说，我们选择了粘结n1和n2，必定就契合了最优树的性质。（也就是说“其他做法都是错”真实不克不及推出“这类做法必定对”，这就像是你在一除夜堆豆子傍边寻觅一个出格的豆子，你拿起一个，看看不是，扔损掉落踪落，又拿起一个，还不是，扔损掉落踪落，消弭到末尾只剩一个豆子了，假定你又晓得这个出格的豆子必定存在，那么这个时辰你根柢不必看就晓得这个豆子必定就是你要找的）那么，你可否直接证实，拼装最优树的过程每步都契合最优树的性质呢？