书名:《算法图解》(原文书名:《Grokking Algorithms》,作者:Aditya Y. Bhargava,译者:袁国忠) 购买链接:中译版 , 原版

简短点评:爱因斯坦说,“如果你不能把它解释给你外婆听,那么你就没有弄明白。”(You do not really understand something unless you can explain it to your grandmother.)用来解释这本用心的书再合适不过。真的弄明白了才能把文绉绉的理论说成大白话。这是一本鼓励人学习计算机算法的好书。

前言:这篇是「威玲旺卡Aileen」在读过中译版的《Grokking Algorithms》后的笔记。转载笔记不用注明我,但请注明原书作者和译者,及标注链接到购买链接,谢谢。

第1章:二分查找(Binary Search)+ 时间复杂度O

二分查找:对数时间 O(log n) ,前提:有序
简单查找 (Simple Search):线性时间O(n)

第2章:选择排序(Selection Search)+ 数组(Array)+ 链表(List)

数组:读取 O(1) 插入 O(n) 删除 O(n)
链表:读取 O(n) 插入 O(1) 删除 O(1)
混合数据:链表数组
选择排序:O(n^2)

第3章:递归(Recursion)+栈(Stack)

循环都可以用递归取代
基线条件(Base Case)+ 递归条件(Recursive Case)
调用栈(Call Stack) FILO

第4章:快速排序(Quick Sort)+分而治之(Divide & Conquer)

D&C:关键1. 找出基准条件 2. 每次递归缩小问题规模
D&C:不是一种解决算法,而是一种解决思路
拓展:欧几里德算法
快速排序:选择一个基准值(Pivot),分成两个分区(Partition),对分区进行快速排序
拓展:归纳证明。需要基线条件,归纳条件,就如同递归
运行时间:快速排序的平均情况是O(n log n),最糟糕是O(n^2)
拓展:合并排序(Merge Sort)的运行时间是O(n log n)
O的常量影响:合并排序的常量比快速排序大。所以在平均情况下,快速排序更快。

第5章:散列表,a.k.a. 哈希表(Hash Table)

散列表所有操作时间都是常量时间O(1)
Python dict() 或 {}
应用场合:仿真映射,防止重复给flag,缓存/记住数据
冲突(Collision):指产生的相同散列函数地址,解决方法是加链表(链地址法),拖慢散列表速度是缺点
防止冲突:1. 及时调整长度(Resizing),保持较低的填充因子(<0.7)2. 用好的散列函数(SHA)

第6章:广度优先搜索(Breadth-First-Search,BFS)+ 图(有向/无向)+ 队列(Queue)

例子:在FB找芒果销售商,从一度关系到二度关系类推
Python deque()
复杂度:O(V+E)V指顶点(vertices),E指边(edges),O(V+E)是因为队列需要检查每个顶点,而搜索需要过每条边。
因为检查顺序很关键,所以需要先进先出的队列,最终才能得到最短距离。
最短序列问题 -> 图建模 -> 用广度优先搜索解决

第7章:狄克斯特拉算法(Dijkstra's Algorithm)+ 加权图(Weighted Graph)

算法过程:1. 找出最便宜的节点; 2. 遍历邻居,如果有前往它们的更短路径,就更新开销; 3. 重复,直到找过每个节点 ;4. 计算最终路径。
只用于有向无环图(Directed Acyclic Graph, DAG)
负权边用贝尔曼-福德算法(Bellman-Ford Algthorithm)
3个散列表实现Dijkstra:1. Graph 2. Costs 3. Parents

第8章:贪婪算法 (Greedy Algorithm)+ NP完全问题(NP-completeness)+ 集合 (Set)

贪婪算法:一直取最优解
Python set()
集合覆盖问题:广播电台企图覆盖所有州,复杂度O(2^n),可以用近似算法求近似最优解
旅行商问题(Travelling Salesman Problem):复杂度O(n!)
NP完全:求近似解更可行
如何识别可能的NP完全:1. 元素少时很快,速度随着元素变多而速度迅猛下跌 2. 所有组合问题 3. 不能用D&C降解 4. 设计序列,如旅行商问题(Travelling salesman problem),设计集合,如广播台集合问题 5. 可以转换为集合覆盖问题或者旅行商问题的都是NP完全问题。

第9章:动态规划 (Dynamic Programming, DP)

动态规划用于求在约束条件下的最优解,在问题可分解为彼此独立且离散的子问题时。
背包问题
动态规划的解决一定涉及网格,单元格的值就是要优化的值,每个单元格都是一个自问题,所以应该考虑如何将问题分成子问题。这有助于找到网格的坐标轴。
例:找最大公共字串和最大公共序列
应用:git diff,levenshtein距离,Microsoft Word行断
计算动态规划方案的公式按情况不同而变化

第10章:K最近邻(K Nearest Neighbor, KNN)

分类就是编组,回归就是预测
除了用欧几里得距离作为距离公式,还有余弦相似度(Cosine Similarity)
应用:OCR,邮件分类用到了朴素贝叶斯分类(Naive Bayes Classifier),预测股票
选取的特征关系KNN的成败

第11章:展望

二叉查找树(Binary Tree):操作平均情况复杂度O(log n)。相关:B树,红黑树,堆,伸展树。
反向索引,创建搜索引擎
傅里叶变换,时域->频域
并行算法。MapReduce,工具Apache Hadoop,映射函数Map,归并函数Reduce
布隆过滤器,一种概率型数据结构,可能错报,但不可能漏报
Hyperloglog,类似布隆过滤器
SHA算法,应用相同文件/检查密码
Simhash局部敏感,SHA局部不敏感
Diffie-Hellman,RSA密钥,公钥+私钥
线性规划,图是线性规划的一个子集

复杂度集合:

二分查找:O(log n)
简单查找:O(n)
选择排序:O(n^2)
合并排序:O(n log n)
快速排序:O(n log n)
旅行商问题:O(n!)
二叉查找树:O(log n)
散列表一项操作:O(1)
集合覆盖问题:O(2^n)
广度优先搜索:O(V+E)

最后更新时间:2017年8月