没有万能的数据结构和算法（总装）

复习

• 排序：多种排序在时间、空间、稳定性上各有取舍
• 树、堆、哈希：不同结构适合不同操作
• 动态规划、贪心、回溯：不同算法范式

TL;DR

• 没有一种结构或算法，在所有场景都最优
• 选择要综合操作、规模、时空与可读性
• “更高效”常常意味着更复杂或更受限
• 理解取舍，比记住答案更重要

正文

　　这是数据结构与算法部分的最后一章。我们从“数据为什么要组织”出发，走过了线性结构、哈希、树、图、排序，最后到算法设计的几种范式。现在把它们收束成一句话：没有万能的答案，只有合适的取舍。

回顾：每个结构都有脾气

　　先快速回看这一路的结构，它们各自擅长什么、又牺牲了什么：

　　排序算法也是同理：归并稳定但要空间，快排就地但最坏会退化，堆排稳定地 O(n log n) 但常数大，计数／基数排序能线性却依赖取值范围。每一个“优点”背后，几乎都站着一个“代价”。

怎么选

　　面对一个新问题，可以从几个角度问自己：

• 主要做哪些操作？ 查找多、还是增删多？
• 数据规模多大？ 小到几十个，还是大到上亿？
• 有没有额外要求？ 是否需要有序？是否需要稳定？
• 资源限制如何？ 内存紧不紧张，数据能否装进内存？
• 实现复杂度可接受吗？ 值不值得为性能引入复杂结构？

　　把这些问清楚，选择往往就不言自明了。

更重要的，是判断力

　　学到这里，真正有价值的东西，可能不是记住某一种结构或算法，而是获得一种判断力：

• 知道每个方案在什么前提下才成立
• 知道“更快”通常意味着更复杂或更受限
• 知道要先弄清问题、再选工具，而不是拿着锤子找钉子

　　这也呼应了整个系列反复强调的主线：没有银弹，只有权衡；没有最好，只有最合适。

接下来

　　到这一章为止，我们已经有了数组、栈、树、哈希表和图，也学会了搜索、递归、贪心、动态规划和回溯。这些工具，足以支撑我们去打开一个从很早就留下的黑箱了——

　　还记得讲程序与编程基础时，我们说过“编译、汇编、链接的内部暂作黑箱”吗？现在，我们有了足够的工具，可以真正走进去，看看一段普通的源代码，究竟是怎样一步步变成能运行的程序的。那就是接下来的编译原理部分。

思考题 1

　　为什么说“没有万能的数据结构和算法”？

思考题 2

　　面对一个新问题，你会从哪些方面考虑该选择哪种结构或算法？

小结

知识点

• 每种结构与算法都有其擅长的操作与代价
• 选择要综合考虑操作、规模、时间、空间与可读性
• 高效常伴随更复杂或更受限制
• 先弄清问题，再选择工具

参考资料

1. Wikipedia(zh)：数据结构：常见结构及其适用场景
2. Wikipedia(zh)：算法设计：常见算法范式及其取舍

思考题答案（仅供参考）

思考题 1

　　因为每种结构或算法都在某些操作上高效，却在另一些操作上付出代价，或者对数据有额外前提。没有任何一种能在所有场景下都最优。所谓“最好”，只能是相对于某一类具体需求而言。

思考题 2

　　可以从主要操作类型（查找／增删多寡）、数据规模、是否要求有序或稳定、时间与空间限制、数据能否装进内存、以及实现复杂度是否可接受等方面综合考虑，再据此挑选合适的结构与算法。

协议

　　本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

封面图

设计师 | 南国微雪