在校生为了面试,有必要强行记住一些复杂算法如红黑树、KMP等的实现吗?

最近在尝试练习手写基本算法,写到红黑树感觉写不下去了orz...所以想知道,有没有必要花费大量精力强行记忆一些所谓十五大经典算法中很复杂的那些算法的实现呢? 我觉得我问的不好,导致大家普遍在回答应付不是一个好行为,应该了解其原理blablabla。我的想法是这样的,对于没工作的人来说,通过考试(找到工作)是最紧迫的事情了,我觉得这就像高考一样,应考和押题的实用主义更适合智商一般水平一般的人,而现在我疑惑的是我押…
关注者
2,423
被浏览
126,145
quora上有道类似的问题,问的是如何才能增强数据结构和算法的能力,robert love(《Linux Kernel Development》的作者)的答案我认为写得非常好,其中也回答了题主的“是否需要背下来rbtree的实现”,链接在这里:Robert Love's answer to How do I strengthen my knowledge of data structures and algorithms?。简要翻译如下:
-----
现在的学生学习和理解数据结构的方法有问题。

数据结构的良好基础不是对每个数据结构都知道细节怎么实现,都背下来大O复杂度和摊销复杂度,当然知道这些非常好,只是你在工作中很少用到它们,你的职业生涯里几乎不可能让你实现一个红黑树的节点删除算法。但是!!你必须知道什么时候BST对于一个问题是个有效的解法。

所以,两个建议:
1. 可视化数据结构,把它画出来,在你的脑海中可视化,可以更好地帮助你直观地理解它。(推荐两个数据结构可视化网站:Data Structure VisualizationVisuAlgo - visualising data structures and algorithms through animation
2. 学习什么时候以及如何将不同的数据结构运用到自己的代码里。忘掉细枝末节的东西,而更关注:什么时候需要hash?什么时候需要tree?什么时候最小化堆是正确的答案?

算法学习推荐:算法导论
算法具体实现书籍:Algorithms in C++, ALgorithms in Java
-----

robert的回答给了一个很好的思路,不仅在数据数据结构这门课上可以应用,也可以帮助在其它一些基础课的学习上,我谈一下自己的理解:

学习操作系统,需要理解为什么会有OS这个东西,如何没有OS会怎么样;OS提供给用户哪些抽象、它又是怎么管理硬件的;进程是怎么管理和调度的,死锁是怎么产生和解决的,内存是怎么管理,文件系统有什么用以及是如何实现的,最好再就一个具体的操作系统(比如xv6)研究这些原理是怎么应用的;而不是开机启动的详细步骤,当然你知道最好。

学习计算机组成原理,需要理解的是为什么在这个高级语言泛滥的时代我们还需要学习汇编,计算机是如何一步一步发展到如今这个组成结构的,为什么单周期实现的cpu效率不高,之后的流水线cpu是如何改进单周期的以及其设计中的挑战是什么,由流水线引发的hazard有哪些以及怎么处理,forwarding又是怎么实现;而不需要背下来每一级流水线寄存器是哪些,因为现代cpu实现一般都是15级以上的流水线stage,除非你是cpu设计者否则背了根本没用。

学习计算机体系结构,需要理解常用的并行方法,并知道每一种并行方法里的具体手段,比如instruction-level parallelism中,需要理解Instruction pipelining,Out-of-order execution,Register renaming,Speculative execution等技术到底干了什么达到改善的目的,知道这些的目的是为了帮助你在程序里合理地组织代码和数据来最好地发挥CPU功能,而不是为了让你设计一个新的CPU。另外,处理器设计中包括了许多工程实践中的很好的原则,学习它可以帮助你理解和解决别的领域的问题。

学习编译原理,需要理解的是一个编译器实现的几个步骤(词法分析、语法分析、语义分析、运行时环境、中间代码、代码生成、代码优化)以及一些关键算法。学词法分析你需要理解状态机、学语法分析你至少需要知道LL自顶向下和LR自底向上的算法,以及为什么需要把我们的程序转成抽象语法树。学运行时环境需要理解程序是怎么存储、装载和执行的。代码优化的时候需要知道最常见的优化方法。

学习计算机网络,需要理解的是整个全球互联网是怎么运作的以及5层模型(应用层、传输层、网络层、数据链路层、物理层)中上层和下层是怎么交互的。可能对大部分开发者有用的是应用层和传输层TCP/UDP的原理,重点是TCP原理的理解:为什么TCP是一个可靠协议?它为了“可靠”付出了什么代价?TCP为什么要握3次手而不是4次5次6次?为什么结束TCP连接需要4次挥手而不是5次6次?TCP的重传机制是怎么实现的?为什么要引入滑动窗口的概念?以及需要理解Congestion control的核心算法是怎样的。

学习数据库原理,重点不是让你知道sql怎么写,而是让你理解如何设计正确的schema,在这个过程中为了消除数据冗余、插入/删除/修改异常会逼着你理解那几种范式(1NF、2NF,3NF,BCNF),以及思考一个功能完整、效率高的数据库是怎么实现,重点是原理的学习,比如在学习transaction的ACID性质的时候,这四点分别代表什么意思,以及是怎么实现它们的?如何实现一个高效的数据库这个话题就太大了,不展开了。

总结一下,为了让自己更高效地学习这些课,介绍一个我一直在用的方法,就是在学习这些课的同时,不断地问自己,“这个设计/算法为什么是这样的,而不是那样的。如果让我来解决这个问题,我会怎么做”。

update:
大一大二计算机相关专业的新生很容易搞不清楚这些基础课程的关系,导致学得非常累。其实,这些基础课不是计算机领域这张大地图上零散的点,它们可以通过“抽象”来实现“分层”,“分层”的目的是让你更容易看清楚这些课的关系,我之前写过一篇文章来解释这个事情:抽象与计算机课程lifeofzjs.com/blog/2016),希望对初学者有帮助。