【不周山之算法与数据结构】壹 总览

学了这么多年计算机和编程,在快要步入社会之前,在不断地碰壁和尝试之后,终于摸到了一点门路。这个系列的文章,更接近于编程入门指南,讲的是从数据结构到算法最终到解决问题的方法和思路。


系列文章

基本上编程中重要的内容,都在这里了。

正文

我想,对于大多数经历过或者正在经历从校园转入社会的人来说,找工作本身就是一个很好的学习过程。如果想要成为一个程序员,尤其是在北美的话,那么刷题(也就是做各种数据结构算法的题目)就是必不可少的了,颇有应试教育的味道。

学习并不是为了考试,可是分数是简单粗暴评判学习效果的方法;编程并不是为了刷题,可是能否给出解答是简单粗暴评判编程水平的方法。虽然不合理不科学,但是在人力物力有限的条件下,这就是游戏规则。

在这个过程中,你会发现,聪明人,或者说善于学习的人,很快就会从应试模式转变为探索模式。题目背后是知识,不同的知识点交织成为学科,死记硬背只能解决见过的问题,但是如果在这个过程中培养了逻辑推理的能力,哪怕遇到一个『新』问题,也能通过类比,找到用『旧』方法稍微变化就可以解决的途径。

如果了解了计算机发展的历史,就会发现,所有现在看起来非常复杂的东西,都是建立在非常简单的基础——零和一——之上的。从最简单的基本类型,到数据结构和算法,通通都是为了解决实际问题而产生的高效解决方案。的确,无论是计算机科学,还是编程,都是非常大的话题,但是并不意味着起跑会很难。在我看来,需要了解的内容,大概有下面这几类(这里参考了 Google 面试指南的部分内容):

  1. 掌握一门基本的编程语言。最好是强类型,支持面向对象编程(比如 C++/Java/C#)的语言。这里说的掌握,不仅仅是语法,而是对语言本身的一些设计特点和具体实现方式的理解。
  2. 能够以 Big O 的方式去分析一个算法的时间/空间复杂度,这样才有一个标准的方式去分析算法的效率。
  3. 基本数据结构的理解和使用,比如
    • 哈希表 Hashtable,及其背后所代表的哈希的思想是如何应用的不同问题的,如果只能用数组来实现,要如何实现
    • 树 Tree, 树的构建(trie),遍历和修改。遍历包括 BFS 和 DFS(前序中序后序),及其对应的思想。如果了解至少一种平衡树(及实现方式)就更好了。
    • 图 Graph,图的三种表达方式及优缺点,基本的遍历算法(还是 BFS 和 DFS),知道这些算法的复杂度以及权衡利弊。如果了解一些如 Dijkstra 和 A* 算法就更好了。
    • 其他的数据结构:堆栈队列链表
  4. 基本算法的理解和使用,比如排序和搜索,以及递归和动态规划。nlogn 时间的排序,logn 时间的搜索。以及了解什么是 NP 问题(旅行商等等)。
  5. 基本的数学知识,排列组合及概率,和一些公式化简。这里可能还可以算上正则表达式。
  6. 操作系统,编译器,及计算机系统的基本知识。比如说进程线程,互斥锁信号量,死锁出现的条件及如何避免,进程线程的资源和上下文切换,多核处理的相关知识。重要的是对计算机相关工具的理解,除了上面提到的,还有 shell 之类的用法。
  7. 基本的设计能力。面向对象设计,代码风格及优化。
  8. 如何清晰表达自己的想法,去快速构建一个问题的解决方案。

还是那句话,刷题仅仅只是一个效率很低的练习过程,真正的学习是进行『刻意练习』,也是我这个系列文章中想要强调的内容。

一通百通,悟道之后就会发现,一招一式固然重要,但那些都是基础,更重要的是解决问题的方法和思路,这,可能就需要多动一点脑子了。

最后说一下大概的写作内容的范围:

  • 正文部分力争简明扼要,说重点,说思想,注意语言逻辑和风格
  • 不贴大段的代码,而是会在文章最后给出题目分类及对应链接
  • 会挑选重点,经典题目进行思路讲解

参考书目:

  • 《Data Structures & Other Objects Using Java》 Michael Main, Fourth Edition (Addison-Wesley Longman, ISBN-13 978-0132576246)
  • 《Introduction to Algorithms》Corman, et al., 1990, MIT Press, ISBN 0262031418
捧个钱场?