第一章 算法简介

二分查找
binary_search 
运行时间 对数时间 
大O表示法 最坏情况
常见的大 O 运行时间 
O(logn)  对数时间 二分查找
O(n)      线性时间 简单查找
O(n*logn)  快速排序 
O(n^2) 选择排序 
O(n!)  旅行商问题 

二分查找的速度比简单查找要快很多，数据越大，优势越明显



第二章 选择排序

数组和链表
需要存储多个元素时，可使用数组或链表
数组的元素都是连在一起的，就像一节节车厢
链表的元素是分散开的，其中每个元素都存储了下一个元素的地址。
数组 适合随机访问
链表的插入和删除的速度很快
在同一个数组中，所有元素的类型都必须相同 



 

第三章 递归
基线条件（ base case）和 递归条件（ recursive case）
栈
函数调用栈
递归指的是调用自己的函数 
栈有两种操作 压入和弹出 
所有函数调用都进入调用栈
调用栈可能非常长，所以讲占用计算机大量的内存
递归容易理解，但是性能比循环差




第四章 快速排序
分而治之
D&C算法包括两个步骤
(1) 找出基线条件，条件必须尽可能简单。
(2) 不断将问题分解（或者说缩小规模），直到符合基线条件

快速排序
基线条件 空数组或只包含一个元素的数组
随机选择基准值元素 或者直接找中间的元素
平均运行时间 O(nlog n)
不稳定的排序算法


第五章 散列表
缓存
冲突（ collision ） 
hashmap 数组+链表
避免冲突
较低的填装因子
良好的散列函数
去重


第六章 广度优先搜索（ breadth-first search， BFS）
广度优先搜索不仅查找从A到B的路径，而且找到的是最短的路径
队列 先进先出 First In First Out  FIFO
栈   后进先出Last InFirst Out LIFO 
人际关系网中搜索芒果销售商
将沿每条边前行 运行时间 O(边数)
队列 检查的每个人 时间为O(人数)
广度优先搜索的运行时间为O(人数 + 边数)
O(V + E)，其中V为顶点（ vertice）数， E为边数

按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列



第七章 狄克斯特拉算法

应用场景 路由协议选路
广度优先搜索，它找出的是段数最少的路径
狄克斯特拉算法（ Dijkstra’s algorithm）找的是最快的路径
广度优先搜索来查找两点之间的最短路径，段数最少
狄克斯特拉算法中，给每段分配一个数字或权重，找出总权重最小的路径

狄克斯特拉算法包含4个步骤
(1) 找出“代价最低”的节点，即可在最短时间内到达的节点。
(2) 对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。
(3) 重复这个过程，直到对图中的每个节点都这样做了。
(4) 计算最终路径。
带权重的图称为加权图（ weighted graph），不带权重的图称为非加权图（unweighted graph）
计算非加权图中的最短路径，可使用广度优先搜索
计算加权图中的最短路径，可使用狄克斯特拉算法
狄克斯特拉算法只适用于有向无环图

最短路径并不一定是物理距离，也可能是让某种度量指标最小
如果有负权边，就不能使用狄克斯特拉算法

小结
1. 广度优先搜索用于在非加权图中查找最短路径
2. 狄克斯特拉算法用于在加权图中查找最短路径
3. 仅当权重为正时狄克斯特拉算法才管用
4. 如果图中包含负权边，请使用贝尔曼-福德算法

第八章 贪婪算法
每步都采取最优的做法
每步都选择局部最优解，最终得到的就是全局最优解
背包问题
有若干物品，每个物品有自己的价值和重量 背包有总重量
问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到
这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别
物品的权重值就是指物品的价值除以物品的质量
每一次的最佳选择就是每次都选出权重值最大的物品
 
近似算法
获得精确解需要的时间太长时，可使用近似算法
判断近似算法优劣的标准如下
速度有多快
得到的近似解与最优解的接近程度

NP 完全问题(Non-deterministic Polynomial多项式的不确定性)
NP完全问题的简单定义是，以难解著称的问题
如旅行商问题和集合覆盖问题
如果能够判断出要解决的问题属于NP完全问题，
就不用去寻找完美的解决方案，使用近似算法即可


元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢
涉及“所有组合”的问题通常是NP完全问题
不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题
如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题
如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题
如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题

小结
1. 贪婪算法寻找局部最优解，以这种方式获得全局最优解
2. 对于NP完全问题，还没有找到快速解决方案
3. 面临NP完全问题时，最佳的做法是使用近似算法
4. 贪婪算法易于实现、运行速度快，是不错的近似算法


第九章 动态规划
先解决子问题，再逐步解决大问题
仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用
动态规划可在给定约束条件下找到最优解
在背包问题中，在背包容量给定的情况下，装下价值最高的商品
每种动态规划解决方案都涉及网格
小结
1. 需要在给定约束条件下优化某种指标时，动态规划很有用
2. 问题可分解为离散子问题时，可使用动态规划来解决
3. 每种动态规划解决方案都涉及网格
4. 单元格中的值通常就是要优化的值
5. 每个单元格都是一个子问题，因此需要考虑如何将问题分解为子问题
6. 没有放之四海皆准的计算动态规划解决方案的公式


第十章 K最近邻算法

KNN可以用来做两项基本工作 分类和回归
1. 分类就是编组
2. 回归就是预测结果（如一个数字）

余弦相似度（ cosine similarity）
余弦相似度不计算两个矢量的距离，而比较它们的角度
余弦相似度被广泛用于协同过滤算法中，尤其是Item-base的协同过滤
两个向量间的夹角大小

OCR
光学字符识别（ optical character recognition）
OCR算法提取线段、点和曲线等特征
提取特征，训练 training

垃圾邮件过滤
朴素贝叶斯分类器  Naive Bayes classifier


第十一章 接下来如何做

二叉查找树 binary search tree
 
反向索引
inverted index  常用于创建搜索引擎

并行算法

MapReduce

映射函数
归并函数

布隆过滤器和 HyperLogLog
布隆过滤器是一种概率型数据结构
HyperLogLog  近似地计算集合中不同的元素数

SHA 算法
安全散列算法 secure hash algorithm 

斐波那契数列
Fibonacci sequence  又称黄金分割数列
因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为 兔子数列