《算法图解》精读笔记

写在前面

• 书籍介绍：本书示例丰富，图文并茂，以让人容易理解的方式阐释了算法，旨在帮助程序员在日常项目中更好地发挥算法的能量。
• 我的简评：这本书纯粹讲算法，写作方式挺不过，让你读完并不会感觉算法是很枯燥的东西，反而会觉得算法相当有趣。
• ！！福利：文末有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、按顺序从小往大算

写在后面

• pdf书籍、笔记思维导图、随书代码打包下载地址：https://pan.baidu.com/s/1HTuiD7c3JKyoSqanT1iDqA(提取码：yocb)
• 思维导图在线查看：点击打开
• 得到电子书地址：点击阅读