第一章
二分查找：二分查找是一种从有序数组中间开始搜索的查找算法
大O表示法：大O表示法是一种表示算法速度的表示法，算法速度指的是操作数的增速
按从快到慢顺序列出的5种大O运行时间：
- O(log n)，也叫对数时间，这样的算法包括二分查找
- O(n)，也叫线性时间，这样的算法包括简单查找
- O(n * log n)，这样的算法包括快速排序
- O(n^2)，这样的算法包括选择排序
- O(n!)，这样的算法包括旅行商问题
第二章
数组：数组的元素都是紧靠相连的
链表：链表的元素是分开的，其中每一个元素都储存了下一个元素的地址
数组的读取速度很快（假如要读取最后一个元素，在链表中，你需要知道前一个元素，因为前一个元素储存了下一个元素的地址；在数组中，则不需要，因为你知道每个元素的地址），链表的插入和删除速度很快（当涉及到插入和删除时，只需要修改元素指向的地址；而数组还要考虑内存空间，元素的前后移动）。
数组和链表的运行时间：
| 数组 | 链表 | |
|---|---|---|
| 读取 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 删除 | O(n) | O(1) |
选择排序：选择排序是一种遍历未排序列表找出最值，并多次采取相同步骤实现排序的算法
第三章
递归：递归指的是调用函数自身的函数
每个递归函数都有两个条件：基线条件（函数不再调用自身）和递归条件（函数调用自身）
栈是一种后进先出（Last In First Out，LIFO）的数据结构，栈有两种操作：压入和弹出。
所有函数调用都进入调用栈。当调用另一个函数时，当前函数暂停并处于未完成状态。
当可能面临栈溢出错误（过多的函数调用导致）时，我们考虑使用循环或尾递归（函数的最后一步调用自身）。
第四章
分而治之算法：一种递归式问题解决方法
分而治之算法的两个步骤：
- 找出基线条件
- 不断将问题分解，直到符合基线条件
快速排序：快速排序是一种采用分而治之策略，对数据进行递归式排序的算法
快速排序的三个步骤：
- 选择基准值
- 将数组分成两个子数组（称为分区）
- 对两个子数组进行快速排序
合并排序：合并排序就是把数组分成最小单位，然后通过不断对相邻单位进行排序合并，最终形成一个有序数组
第五章
散列函数：将输入映射到数字
散列函数的要求：
- 同一输入的输出必须是一致的
- 不同的输入映射到不同的数字
散列表：一种结合使用散列函数和数组的数据结构
散列表的应用：查找，防止重复，缓存
冲突：给两个键分配的位置相同。
避免冲突的方法：较低的填装因子（低于0.7）和良好的散列函数（数组中的值呈均匀分布）
第六章
图：图是一种模拟一组链接的方法，由节点和边组成，相邻的节点称为邻居
广度优先搜索：解决最短路径的算法
面临类似最短路径问题时，可采用图来将来模型，再使用广度优先搜索来解决问题
广度优先搜索可回答两个问题：
- 从节点A出发，有前往节点B的路径吗？
- 从节点A出发，前往节点B的哪条路径最短？
队列：队列是一种先进先出（FIFO）的数据结构
有向图：有向图的边带箭头，并指定了关系的方向，其中的关系是单向的
无向图：无向图是没有箭头的，其中的关系是双向的
广度优先搜索的运行时间是O(顶点数+边数)，其中包括队列的运行时间O(顶点数)和搜索过程中时间O(边数)
第七章
权重：每条边上关联的数字
加权图：带权重的图
非加权图：不带权重的图
狄克斯特拉算法：用于在加权图中查找最短路径
广度优先搜索用于在非加权图中查找最短路径
不能将狄克斯特拉算法用于包含负权边的图
如果图中包含负权边，可使用贝尔曼-福德算法
第八章
贪婪算法：每步都采取最优的算法
近似算法：是指用来发现近似方法来解决优化问题的算法，贪婪算法是近似算法之一
NP完全问题：必须计算每个可能的集合，因而还没找到快速解决方案，目前最佳的做法是使用近似算法
- 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢
- 涉及“所有组合”的问题通常是NP完全问题
- 不能将问题分成小问题，必须考虑各种可能的情况，这可能是NP完全问题
- 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题
- 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题
- 如果问题可转化为集合覆盖问题或旅行商问题，那它肯定是NP完全问题
第九章
动态规划：先解决子问题，再逐步解决大问题
动态规划适用于在给定约束条件下优化某指标，问题可分解为离散子问题的情况下。
每种动态规划解决方案都涉及到网格。
第十章
K最近邻算法（KNN）：用于分类（编组）和回归（预测结果）
特征抽取：将物品转换为一系列可比较的数字
能否挑选合适的特征事关KNN算法的成败
第十一章
略
