《算法图解》精读笔记
写在前面
- 书籍介绍：本书示例丰富，图文并茂，以让人容易理解的方式阐释了算法，旨在帮助程序员在日常项目中更好地发挥算法的能量。
- 我的简评：这本书纯粹讲算法，写作方式挺不过，让你读完并不会感觉算法是很枯燥的东西，反而会觉得算法相当有趣。
- ！！福利：文末有pdf书籍、笔记思维导图、随书代码打包下载地址哦
第一章 算法简介
- 1.1. 二分查找的速度比简单查找快得多
- 1.2. O（log n）比O（n）快。需要搜索的元素越多，前者比后者就快得多
- 1.3. 算法运行时间并不以秒为单位
- 1.4. 算法运行时间是从其增速的角度度量的
- 1.5. 算法运行时间用大O表示法表示
第二章 选择排序
- 2.1. 计算机内存犹如一大推抽屉
- 2.2. 需要存储多个元素时，可使用数组或链表
- 2.3. 数组的元素都在一起
- 2.4. 链表的元素是分开的，其中每个元素都存储了下一个元素的地址
- 2.5. 数组的读取速度很快
- 2.6. 链表的插入和删除速度很快
- 2.7. 在同一个数组中，所有元素的类型都必须相同（都为int、double等）
第三章 递归
- 3.1. 递归指的是调用自己的函数
- 3.2. 每个递归函数都有两个条件：基线条件和递归条件
- 3.3. 栈有两种操作：压入和弹出
- 3.4. 所有函数调用都进入调用栈
- 3.5. 调用栈可能很长，这将占用大量的内存
第四章 快速排序
- 4.1. D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组
- 4.2. 实现快速排序时，请随机地选择用作基准值得元素。快速排序的平均运行时间为O（nlog n）
- 4.3. 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快得原因所在
- 4.4. 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O（log n）的速度比O（n）快得多
第五章 散列表
- 5.1. 散列表是一种功能强大的数据结构，其操作速度快，还能让你以不同的方式建立数据模型
- 5.2. 可以结合散列函数和数组来创建散列表
- 5.3. 冲突很糟糕，应使用可以最大限度减少冲突的散列函数
- 5.4. 散列表的查找、插入和删除速度都非常快
- 5.5. 散列表适合用于模拟映射关系
- 5.6. 一旦填装因子超过0.7，就该调整散列表的长度
- 5.7. 散列表可用于缓存数据（例如，在web服务器上）
- 5.8. 散列表非常适合用于防止重复
第六章 广度优先搜索
- 6.1. 面临类似于寻找最短路径的问题时，可尝试使用图来建立模型，再使用广度优先搜索来解决问题
- 6.2. 图由节点（node）和边（edge）组成
- 6.3. 对于检查过的，务必不要再去检查，否则可能导致无限循环
第八章 贪婪算法
- 8.1. 贪婪算法寻找局部最优解，企图以这种方式获得全局最优解
- 8.2. 对于NP完全问题，还没有找到快速解决方案
- 8.3. 面临NP完全问题时，最佳的做法是使用近似算法
- 8.4. 贪婪算法易于实现、运行速度快，是不错的近似算法
- 8.5. 经典的背包问题（重量和价值）
- 8.6. 三步走（来自知乎）：1、明确到底什么是最优解；2、明确什么是子问题的最优解；3、分别求出子问题的最优解再堆叠出全局最优解
第九章 动态规划
- 9.1. 需要在给定约束条件下优化某种指标时，动态规划很有用
- 9.2. 问题可分解为离散子问题时，可使用动态规划来解决
- 9.3. 每种动态规划解决方案都设计网格
- 9.4. 单元格中的值通常就是你要优化的值
- 9.5. 每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题
- 9.6. 没有放之四海皆准的计算动态规划解决方案的公式
- 9.7. 经典的旅行商问题（城市路径选择）
- 9.8. 三个子目标（来自知乎）：1、建立状态转移方程；2、缓存并复用以往结果；3、按顺序从小往大算
写在后面
