一、信息

[200821]《算法图解》 /作者: [美] Aditya Bhargava / 人民邮电出版社
2020阅读目标达成：12/30

二、简评

★★★★★ 看过《我的第一本算法书》后又看的这本《算法图解》，这本书明显更加系统化、更加生动一些。虽然不是程序员或工作相关，了解算法对于锻炼自己的思维还是很有帮助的。

三、摘录

下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。

• O(log n)，也叫对数时间，这样的算法包括二分查找。
• O(n)，也叫线性时间，这样的算法包括简单查找。
• O(n * log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
• O(n2)，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
• O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。

我很喜欢Leigh Caldwell在Stack Overflow上说的一句 话： “如果使用循环， 程序的性能可能更高； 如果使用递归， 程序可能 更容易理解。 如何选择要看什么对你来说更重要。 ”

使用栈虽然很方便， 但是也要付出代价： 存储详尽的信息可能占用大量 的内存。 每个函数调用都要占用一定的内存， 如果栈很高， 就意味着计 算机存储了大量函数调用的信息。 在这种情况下， 你有两种选择。 重新编写代码， 转而使用循环。 使用尾递归 。 这是一个高级递归主题， 不在本书的讨论范围内。 另外， 并非所有的语言都支持尾递归 递归指的是调用自己的函数。 每个递归函数都有两个条件： 基线条件和递归条件。 栈有两种操作： 压入和弹出。 所有函数调用都进入调用栈。 调用栈可能很长， 这将占用大量的内存。

Facebook实际使用的是什么呢？很可能是十多个数据库，它们基于众多不同的数据结构：散列表、B树等。数组和链表是这些更复杂的数据结构的基石。