为什么算法这么难？BY 刘未鹏
广大码农同学们大多都有个共识，认为算法是个硬骨头，很难啃，悲剧的是啃完了还未必有用&&除了面试的时候。实际工程中一般都是用现成的模块，一般只需了解算法的目的和时空复杂度即可。不过话说回来，面试的时候面算法，包括面项目中几乎不大可能用到的算法，其实并不能说是毫无道理的。算法往往是对学习和理解能力的一块试金石，难的都能掌握，往往容易的事情不在话下。志于高者得于中。反之则不成立。另一方面，虽说教科书算法大多数都是那些即便用到也是直接拿模块用的，但不幸的是，我们这群搬砖头的有时候还非得做些发明家的事情：要么是得把算法当白盒加以改进以满足手头的特定需求；要么干脆就是要发明轮子。所以，虽说面试的算法本身未必用得到，但熟悉各种算法的人通常更可能熟悉算法的思想，从而更可能具备这里说的两种能力。那么，为什么说算法很难呢？这个问题只有两种可能的原因：
算法本身就很难。也就是说，算法这个东西对于人类的大脑来说本身就是个困难的事儿。
讲得太烂。下面会说明，算法之所以被绝大多数人认为很难，以上两个原因兼具。我们说算法难的时候，有两种情况：一种是学算法难。第二种是设计算法难。对于前者，大多数人（至少我当年如此）学习算法几乎是在背算法，就跟背菜谱似的（&Cookbook&是深受广大码农喜爱的一类书），然而算法和菜谱的区别在于，算法包含的细节复杂度是菜谱的无数倍，算法的问题描述千变万化，逻辑过程百转千回，往往看得人愁肠百结，而相较之下任何菜谱涉及到的基本元素也就那么些（所以程序员肯定都具有成为好厨师的潜力:D）注意，即便你看了算法的证明，某种程度上还是&背&（为什么这么说，后面会详述）。我自己遇到新算法基本是会看证明的，但是发现没多久还是会忘掉，这是死记硬背的标准症状。如果你也啃过算法书，我相信很大可能性你会有同感：为什么当时明明懂了，但没多久就忘掉了呢？为什么当时明明非常理解其证明，但没过多久想要自己去证明时却发现怎么都没法补上证明中缺失的一环呢？初中学习几何证明的时候，你会不会傻到去背一个定理的证明？不会。你只会背结论。为什么？一方面，因为证明过程包含大量的细节。另一方面，证明的过程环环相扣，往往只需要注意其中关键的一两步，便能够自行推导出来。算法逻辑描述就好比定理，算法的证明的过程就好比定理的证明过程。但不幸的是，与数学里面大量简洁的基本结论不同，算法这个&结论&可不是那么好背的，许多时候，算法本身的逻辑就几乎包含了与其证明过程等同的信息量，甚至算法逻辑本身就是证明过程（随便翻开一本经典的算法书，看几个经典的教科书算法，你会发现算法逻辑和算法证明的联系有多紧密）。于是我们又回到刚才那个问题：你会去背数学证明么？既然没人会傻到去背整个证明，又为什么要生硬地去背算法呢？那么，不背就不背，去理解算法的证明如何？理解了算法的证明过程，便更有可能记住算法的逻辑细节，理解记忆嘛。然而，仍然不幸的是，绝大多数算法书在这方面做的实在糟糕，证明倒是给全了，逻辑也倒是挺严谨的，可是似乎没有作者能真正还原算法发明者本身如何得到算法以及算法证明的思维过程，按理说，证明的过程应该反映了这个思维过程，但是在下文关于霍夫曼编码的例子中你会看到，其实饱受赞誉的CLRS和《Algorithms》不仅没能还原这个过程，反而掩盖了这个过程。必须说明的是，没有哪位作者是故意这样做的，但任何人在讲解一个自己已经理解了的东西的时候，往往会无意识地对自己的讲解进行&线性化&，例如证明题，如果你回忆一下高中做平面几何证明题的经历，就会意识到，其实证明的过程是一个充满了试错，联想，反推，特例，修改问题条件，穷举等等一干&非线
分享这篇日志的人也喜欢
第一天直播????
小辣娇求守护
今天穿的有点女神哈哈
中午，嘿嘿
求你别下雨了?_?
你们的云朵已改名朵儿
热门日志推荐
人人最热标签
北京千橡网景科技发展有限公司：
文网文[号··京公网安备号·甲测资字
文化部监督电子邮箱：wlwh@··
文明办网文明上网举报电话： 举报邮箱：&&&&&&&&&&&&
请输入手机号，完成注册
请输入验证码
密码必须由6-20个字符组成
下载人人客户端
品评校花校草，体验校园广场([已注销])
([已注销])
([已注销])
([已注销])
([已注销])
第三方登录：知其所以然之永不遗忘的算法_开心赚宝_新浪博客
相信大部分同学曾经都学习过快速排序、Huffman、KMP、Dijkstra等经典算法，初次学习时我们惊叹于算法的巧妙，同时被设计者的智慧所折服。于是，我们仔细研读算法的每一步，甚至去证明算法的正确性，或者是去尝试优雅地实现这些算法。总之，我们会花费很大的时间精力去理解这些智慧的结晶。
然而，现在对于这些经典的算法你仍然了然于胸吗？就算现在你仍然记得这些算法的步骤，你敢确保一年后、十年后自己不会忘记？我想没有多少人敢保证吧。
我们当然希望自己掌握一个算法后，就永远不会忘记，最好还能举一反三，利用算法中的思想去解决新的问题。然而，现实与美好的愿景往往是背道而驰，不要说举一反三，我们甚至经常忘记那些算法本身。
背算法与设计算法
为什么会这样？简单来说，因为我们从来就没有真正掌握过这些算法，我们只不过是在背诵别人发明的算法，就像我们背诵历史书上的那些历史事件一样，时间久了自然会慢慢遗忘。
我们接触到某个算法时，看到的只是对算法过程的讲解，对其正确性的证明，或者对其效率的分析（想想大名鼎鼎的《算法导论》
，《算法》是如何讲解某一算法的），我们不会看到那些牛人是如何“灵机一动”设计出了这惊天地泣鬼神的算法。也就是说我们只是知其然，并没有知其所以然。当我们不知道一个算法的来龙去脉，不知道设计它经历的那些思维历程时，就很容易忘记它的具体内容。相反，那些牛人就不会忘记自己设计的算法。
所以，当看到别人牛逼的闪闪发光的算法后，我们一定要探寻算法背后那“曲径通幽”的思维之路。只有经历了思维之路的磨难，才配得上永远占有一个算法，并有可能举一反三，或者是设计一个巧妙算法。刘未鹏在知其所以然（三）：为什么算法这么难？
中探索了Huffman编码的思维历程，值得一看。顺便说一下，探索算法背后的思维历程不是件容易的事，要知道就是霍夫曼本人也是花了一个学期才想出它的编码算法。
下面我们以LeetCode上一个好问题，来探索这个问题的算法背后的思维之路。关于什么是好问题，刘未鹏在跟波利亚学解题
上有一个不错的观点：好问题即测试一个人思维的习惯的题目，通常考察你的联想能力、类比能力、抽象能力、演绎能力、归纳能力、观察能力、发散能力等。
一个好问题
LeetCode 84题：Largest Rectangle in Histogram
，给定一个直方图（下图a），求直方图中能够组成的所有矩形中，面积最大为多少。对于图a来说，我们很容易看出来面积最大的矩形为高度为5和6的直方图组成的矩形（图b隐形部分），其面积为5
* 2 = 10。
求直方图最大面积矩形
其实这个题稍微加以变化，就是另一个相当有趣的问题：Maximal Rectangle
这道题目一个显而易见的解决方法就是暴力搜索：找出所有可能的矩形，然后求出面积最大的那个。要找出所有可能的矩形，只需要从左到右扫描每个立柱，然后以这个立柱为矩形的左边界（假设为第i个），再向右扫面，分别以（i+1,
i+2, n）为右边界确定矩形的形状。
这符合我们本能的思考过程：要找出最大的一个，就先列出所有的可能，比较大小后求出最大的那个。然而不幸的是，本能的思考过程通常是简单粗暴而又低效的，就这个题目来说，时间复杂度为N^2
。那么有没有一种更加高效的解决办法呢？
一个好算法
我第一次面对这个题时，并没有想出一个漂亮的解决方案。因为从给定的条件来看，似乎找不到一个约束条件使得满足这个条件的矩形面积最大，也就是说无法缩减问题的规模，因此必须找出所有可能的矩形，这样的话效率肯定是N^2
然而去Google了一下，立即发现了一个时间复杂度O(n)的算法，当时就被这神奇的解法所震撼到。它的代码十分简单，简单到一开始我根本就看不懂，不明白为什么这样子求出的就是最大的矩形。网上好多所谓的解题报告里面只是人云亦云地给出了算法的步骤，没有算法正确性的证明，更没有我们最想要的关于解题思路。
我也先给出算法步骤和代码，看看你是不是同样一头雾水。在程序中维护一个栈，栈中元素为直方图中bar的下标，然后从头开始扫描每个bar：
如果当前bar的高度大于栈顶bar的高度，则将当前bar的下标入栈；
否则执行出栈操作，记录弹出下标对应的bar的高度，并计算出一个面积，然后用这个面积更新最大面积。
代码也是相当简洁，python源码如下：
def largestRectangleArea(self, height):
height.append(0)
= len(height) no_decrease_stack = [0]
max_size = height[0] i = 0
size: cur_num = height[i] if
(not no_decrease_stack or cur_num
& height[no_decrease_stack[-1]]):
no_decrease_stack.append(i) i +=
1 else: index =
no_decrease_stack.pop() if no_decrease_stack: width =
i - no_decrease_stack[-1] -
1 else: width = i max_size =
max(max_size, width * height[index])
return max_size
高效而难以理解，这就是那些神奇算法的共性。
一个思维历程
那么这个算法真的就是我等凡夫俗子不能想出来的？难道我们只能仰望高山，恨自己智商不高？我还真不服气呢，于是又静下心去思考这个问题。
这次我们不从已知条件推结果，而直接从结论入手，就是说假设现在已经找到了面积最大的那个矩形。接着我们来分析该矩形有什么特征，然后可以用下面两种方法之一来缩减问题的规模（因为这两种方法都不用找出所有的矩形一一比较）。
找出满足这些特征的矩形，面积最大的矩形肯定是其中之一；
排除那些不满足这些特征的矩形，面积最大的矩形在剩下的那些矩形里面。
为了使考虑情况尽可能全面，画了许多直方图，防止使用原题目图片可能存在的一些特定假设，其中一个直方图如下图：
更一般的一个例子
通过不断地对多个直方图的观察，发现面积最大的那个矩形好像都包含至少一个完整的bar，那么这条规律适用于所有的直方图吗？我们用反证法来证明，假设某个最大矩形中每个竖直块都是所在的bar的一小段，那么这个矩形高度增加1后仍然是一个合法的矩形，但新的矩形面积更大，与假设矛盾，所以面积最大的矩形必须至少有一个竖直块是整个bar。
至此我们找到了面积最大矩形的一个特性：各组成竖直块中至少有一个是完整的Bar
。有了这条特性，我们再找面积最大的矩形时，就有了一个比较小的范围。具体来说就是针对每个bar，我们找出包含这个bar的面积最大的矩形，然后只需要比较这N个矩形即可（N为bar的个数）。
那么问题又来了，如何找出“包含某个bar的面积最大的矩形呢
”？对于上面的直方图，包含下标为4的bar的最大矩形如下图橘黄色部分：
简单观察一下，就会发现要找到包含某个bar的最大矩形其实很简答，只需要找到高度小于该bar的左、右边界即可，上图中分别是下标为1的bar和下标为10的bar。
至此问题已经变为“对于给定的bar，如何确定高度比它小的左、右边界”
。其实求左边界和右边界是同样的求法，下面我们考虑求每个bar的左边界。最直接的思路是对于每个bar，扫面其前面所有的bar，找出最后一个高度小于它的bar，这样的话时间复杂度明显又是N^2
，Holy Shit。
到这里似乎没有路可走了，但如果我们继续绞尽脑汁地去想，可能
（或许你对栈理解的很深入，或许是你在一个类似的问题中用到了栈，当然你也可能想到动态规划的思想，那也是可行的）会联想到栈这一数据结构。用栈维护一个高度递增的bar的集合，也就是说栈底到栈顶部对应的bar的高度越来越大。那么对应一个刚读入的bar，我们只需要比较它的高度和栈顶对应bar的高度，如果当前bar比较高，则弹出栈顶元素继续比较，直到栈顶bar比它低或者栈为空。之后，将当前bar入栈，更新栈内的递增序列。
我们从左到右扫一遍得到每个bar对应的左边界，然后从右到左扫一遍得到bar的右边界。两次扫描过程中，每个bar都只有出栈、入栈操作，所以时间复杂度为O(N)。通过这样的预处理，即可以O(N)的时间复杂度得到每个bar的左右边界。之后对于每个bar求出包含它的最大面积，也即是由左右边界和bar的高度围起来的矩形的面积。再做N次比较，即可得出最终的结果。
这里先预处理用两个栈扫描两次得到左、右边界，再计算面积，是按照推导过程一步一步来的。当我们写完程序后，再综合看这个问题，可能会发现其实没必要这样分开来做，我们可以在扫描的同时，维护一个递增的栈，同时在“合适的”时候计算面积，然后更新最大面积。具体实现方法就是前面给出的那个神奇的算法，不过现在看来一点也不神奇了，我们已经探索到了它背后的思维历程。
当然，条条道路通罗马，上面思维过程只是其中一条通往解决方案的路径，你可能以另一种思维过程找到了答案。不过，我们上面的整个推导过程没有涉及一些类似“神谕”的启发，只是一些简单的方法：比如从结论推导、反证法、归纳总结、联想（可能联想到栈有点难）等，因此每个人都可以学会，并且很容易被大脑记住。值得注意的是，我们的整个思考过程并不简简单单地跟上面写的那样是线性的，它更可能是树形的，只是我们剪去了那些后来证明行不通的枝。
解题的万能思考法则?
人类在漫长的进化史中，解决了各种各样的问题。例如
如何度过一条湍急的河流
如何保留火种
如何治愈天花
如何制造一个会飞的机器
同时也对自己的思维方式进行总结和反思，笛卡尔曾经试图将人类思维的规则总结为36条（最终完成了21条
那么有没有一个解题的万能思考法则，按照这个法则去思考，最终能解决所有的问题或者是证明某个问题不可解？目前看来是没有这样的思考法则的，不然我们就可以制造出真正的会思考的机器了。
不过还是有许多思维方法值得我们去学习强化，波利亚在《How To Solve
It》上总结了这些方法，如果想培养良好的思维习惯，那么这本书是必不可少的。
博客等级：
博客积分：0
博客访问：29,411
关注人气：0
荣誉徽章：