## 为什么算法这么难？ 转

oschina_00

1、算法本身就很难。也就是说，算法这个东西对于人类的大脑来说本身就是个困难的事儿。

2、讲得太烂。

1、一劳永逸：程序员都知道“一次编写到处运行”的好处，多省事啊。学了就忘，忘了又得学，翻来覆去浪费生命。为什么不能看了一遍就再也不会忘掉呢？到底是教的不好，还是学得不好？

2、事半功倍：事实上，程序员不仅讲究一次编写到处运行，更讲究“一次编写到处使用”（也就是俗称的“复用”）。如果学一个算法所得到的经验可以到处使用，学一当十，推而广之，时间的利用效率便会大大提高。究竟怎样学习，才能够使得经验的外推（extrapolate）效率达到最大呢？

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

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…

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.

1、觉得理所当然。

2、觉得恍然大悟。

（事实上波利亚在他的著作《How to Solve it》中举的正是这么个例子）

1、作者轻飘飘地就给出了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都没搞定的这个问题花了他一学期，难道他在这个学期里面大脑就一片空白（或者所有的尝试全都是完全不相干的徒劳），然后到学期末尾忽然“灵光一现”吗？

2、如果“仔细观察”:)，我们会发现两个cost function表达中frequency的概念有微妙的差异，在第一个cost function中，只有叶子节点有frequency，而这个frequency必须和叶子节点的深度相乘。而在第二个cost function中，内部节点也具有了frequency，可是所有节点的“frequency”忽然全都不跟深度相乘了。frequency的不同含义令人困惑。

3、作者提到：第一个cost function告诉我们频率最低的两个节点必然处于最优编码树的底端，作为最低内部节点的两个子节点。这是一个不严谨的说法，从前文给出的条件和性质，只能推导出编码树的最底层必然能找到频率最低的两个节点，但它们未必一定要是兄弟节点，如果树的最底层不止能容纳两个节点的话它们就可以有不同的父节点。“我们不妨考虑”这样一个例子：对A,B,C,D四个字母进行编码，假设它们的频率分别是1， 1， 2， 2。这个时候我们可以构造如下图所示的两棵树，两棵树的cost都是12，都是最优的。但其中一棵树中，两个频率最低的节点并非兄弟。

• 在最优霍夫曼树中，无论互换哪两个叶子节点，得到的树都变得更“差”。（严格来说是不会变得更“好”，因为最优树未必唯一）

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

1、不要觉得每个步骤都很显然，每个nontrivial的算法背后都有一段艰辛的探索经历，觉得显然的话必然是一种幻觉。Stay foolish，才能发现某些环节其实并不是那么显然的。

2、检验是否真正理解的最佳方法就是过一段时间之后，自己试着证明一次。如果真正理解了的话，你的证明便会比较顺畅。如果当时没有真正理解，那么凡是那些你当时觉得显然但其实不显然的地方，都会成为你证明里面缺失的环节。

3、对于一个算法，多寻找各种来源的资料，也许能够找到一个讲的比较深刻的。我在《数学之美番外篇：快排为什么那么快》和《知其所以然（一）》里面都举到了这样的例子。

4、多试着去抽象背后的一般性法则，即便后来发现抽象得是错的，也比不去抽象要好。抽象是推广的基础。只有抽象出更深层的法则，才能让你事半功倍，触类旁通，否则一个萝卜永远是一个坑。（注意，其实我们的下意识是会进行一定程度的抽象的，例如前面提到的原始人的例子，小溪和小河（或者小沟）细节上是不同的，但本质上是一样的，我们的大脑会自动进行这种简单抽象，提出事物的共性。正因此，即便你不去有意识地总结一般规律，只要你看的足够多，练的足够多，必然就会越来越谙熟。）

### oschina_00

2015/04/26
33K
150

h4cd
2018/09/04
5.8K
24
2018-3-23论文一种新的群智能算法--狼群算法（框架结构+感想一点点）

luolang_103
2018/03/23
0
0

2018/12/04
3.2K
0
[J+]济南移动互联网沙龙2015年开年专场

2015年，新的起点，新的征程，小伙伴们，无论你在过去的一年有多少遗憾、生活捉弄你多少回，现在都已经自动清零了，此刻的你只会比过去更强大；奋斗的路上少不了泪水和汗水，偶尔停下脚步看看...

2015/01/01
3.7K
28

ksfzhaohui
21分钟前
4
0

25分钟前
3
0
CSS技巧之向下箭头

42分钟前
2
0
SpringCloud alibaba微服务之NACOS多环境配置整合

44分钟前
4
0
tcpdump

tcpdump -A -s0 port 21011 -i any (1)tcp: ip icmp arp rarp 和 tcp、udp、icmp这些选项等都要放到第一个参数的位置，用来过滤数据报的类型 (2)-i eth1 : 只抓经过接口eth1的包 (3)-t : 不显...

mskk
49分钟前
5
0