关于算法学习的总结和感悟

时隔一年重读《算法导论》，去年读到了二叉查找树就搁浅了，今年从头捡起，希望能走的

更远一些。算上大学时的数据结构与算法课，今年可以算是第三波学习攻势了。随着学习的深入，

对算法的学习渐渐有了些自己的看法和感悟。

一.为什么学习算法？

记得初学算法时不明白为什么费力分析程序的执行步骤后，还要用公式表达出来并求极值。

一遍遍的学习渐渐有了领悟：算法研究是用来做大事的！之所以分析效率还求极限，是因为

各种算法和数据结构都要研究其在海量输入数据或最坏最不利的情况下的效率表现。如果

只是我们每天乏味工作中那三两个数的排序，几十个数值对的哈希，那其实怎样实现都无所

谓了。

所以个人觉得，学习算法能提高分析代码、洞察效率的能力，并且它也是我们继续深入学习

操作系统、网络编程、数据库的基础。如操作系统管理内存的红黑树，保存进程优先级的

最大堆，程序运行时函数调用的栈结构，数据库中的B树索引，大量数据的外部多路归并排序

和编译器将表达式解析为树然后遍历等等。所以要想深入计算机科学的内核，算法这一关是

必须过的，这也是我的学习计划。

PS：关于我的学习计划：http://blog.csdn.net/dc_726/article/details/7017781。可以看到算法

是在整个知识体系的最底层部分，这是我宏伟蓝图的基础，呵呵~

如果你学了感觉它没用，其实不是那样的，只是你还没碰到需要它的场合，杀鸡焉用牛刀，

记住它是用来做大事情！

二.算法的学习方法

学习算法如果选择好方法学到最后很可能就什么都不记得了，就像我第一次读《算法导论》时

一样，也仔仔细细的看了，还做了些习题，可读完过后感觉什么都没掌握一样。这次重读，我

找到了适合自己的方法：

1.《算法导论》中几乎每个数据结构与算法都会有对应的例子和图示用来生动讲解。光看一遍

还不够，拿起笔跟着例子走一遍算法的伪代码，看看算法每一步中的值、状态是怎么变化的。

这样才能把例子搞透，不然白瞎了《算法导论》里一幅幅那么清楚明了的图示了。

2.搞懂例子，自然就要实现算法了。不管算法多么简单，一定要自己动手实现，切忌手懒啊。

实现好一个个算法的代码都保存备份好，这也是一笔财富，而且很有成就感。 关于具体用什么

语言来实现稍后再说。

3.只是搞清楚了基本的算法还不够，《算法导论》每节后还有不少有价值的习题，特别是每章

最后都有一些思考题，其中有的是数据结构进行扩展的，有的是算法的实际应用，一定要好好

研究才能更深的理解这一节的知识。

例如堆思想的应用：http://blog.csdn.net/dc_726/article/details/7285040

例如二叉树的变种：http://blog.csdn.net/dc_726/article/details/7391988

4.最后一定要记笔记，不管是手写的还是博客。笔记不仅方便以后的查找，记笔记的过程也会

激发你大脑思考，很多奇思妙想都是动笔头时冒出来的。

有关笔记及一些记录工具：http://blog.csdn.net/dc_726/article/details/7068357

记住：学习并不浪费时间，浪费时间的是重复学习！

三.实现语言的选择

大学时的数据结构课要求使用的是C++，后来我第一遍学《算法导论》时用的是我最习惯的

Java，而现在第二遍学习时我用的却是C。不用我最熟悉的Java而用C的原因是C语言的简洁

和指针的强大，这一点在实现复杂一些的数据结构时体现的尤为突出。并且很多底层的东西

如操作系统、编译器等也都是C的地盘，因此同时学习C语言和算法对未来的深入学习有着

极为重要的作用。暂时放下我的老朋友Java，拥抱C！

四.要把握本质

初学算法时，搞不清楚为什么有那么多的数据结构，那么多的排序算法。散列表不是已经很好

了吗，为什么又搞出一堆二叉树？快排不是已经很完美了吗，为什么还有堆排、冒泡、合并排？

一遍遍地学习，学会比较各种数据结构和算法后，才能看清这些的设计背后的本质。

1.各种排序

快速排序的确很完美了，但其他排序方法也是有他们的用武之地的。对于输入数据范围已知时，

如输入数据都是0到10之间的整数，那么计数排序就可以上场了。又如当输入数据是海量的，

没法一次全部拿到内存中排好时，可以将输入数据分成多块，每块拿到内存中排序，之后对每

个排好序的块进行多路归并。

快速排序：http://blog.csdn.net/dc_726/article/details/7292361

多路归并：http://blog.csdn.net/dc_726/article/details/7262665

2.堆、栈及链表

堆、栈、链表都是再简单不过的数据结构了，但我们学习时不能就局限于对简单应用的掌握，

这些简单结构在特定场景或与其他数据结构结合起来使用时会产生巨大的威力。如堆在K路

归并中与其他内排序的配合，用栈来实现递归调用（如二叉树的非递归中序遍历）等。

二叉树遍历：http://blog.csdn.net/dc_726/article/details/7391288

3.哈希与红黑

散列表性能很好，可是当需要随时动态插入数据时，随着数据越来越多，散列表中的冲突数据

也越来越多，这样的静态散列自然要性能下降。可是红黑树却可以保证树的高度从而保证效率，

所以尽管红黑树很复杂，但它却是维护动态集合的不错选择。然而散列表也是与时俱进的，

动态哈希能够在散列表中数据增多到一定量时自动增大散列表，并重新哈希。这就需要较大的

存储空间，但现今的内存白菜价，所以散列表也可以维护动态数据集合了，所以memcached火

起来了。

4.树家族

平衡树家族很庞大，有AVL树、红黑树、Treap树以及Size平衡树（SBT）。但学习时要把握住

他们的本质：他们都是平衡二叉树，区别只是在如何保持树的高度不会过高上。为何关注树的

高度？因为平衡二叉树上各种操作的性能都是由树高来决定的。

此外常见的还有基数树和Trie树。在树结点中保存01或者各种字符，用于排序01串以及文本统计。

Trie树的应用：http://blog.csdn.net/dc_726/article/details/7163466

五.算法的等级修炼 

我心中对算法有个模糊的分级，学习时可以设定自己短期或长期想要达到的目标。

现在快要第二次学完《算法导论》基础部分的十四章了，也只是了解的程度，才刚刚开始有些

感悟。都说算法是内功，学习起来需要旷日持久、小火慢熬，所以还要努力啊！

1.了解：了解各种算法和数据结构的基础知识，但对他们的具体应用范围一头雾水。

2.掌握：能够清楚明白各种算法的优劣，并开始学会比较他们的应用场景。

3.选择：至此各种结构与算法已经在我们的锦囊里了，碰到问题时要学会从中拿出合适的。

4.扩展：根据具体问题对现有算法进行简单的扩展和改造，并进行效率分析。

5.设计：能为现实生活中复杂的问题设计全新的数据结构或算法来解决。

结束语

算法是美妙而迷人的，但越深入就需要越强的数学功底。每个人可以根据自己的兴趣浓淡、

个人能力为自己制定目标。我自知自己没有那么强的能力，所以个人制定目标等级是3和4

之间，也就是能够应用这些现有的数据结构和算法，能简单的扩展和分析就可以了。希望

大家也都能为自己制定合适的目标，重要的是享受算法的学习过程。切忌走火入魔啊，哈哈！