《算法图解》读书笔记

一、信息

[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树等。数组和链表是这些更复杂的数据结构的基石。

2 Replies to “《算法图解》读书笔记”

wys进行回复 取消回复

电子邮件地址不会被公开。 必填项已用*标注