Ai-Reads：《算法图解》读书笔记
2017-08-27 本文已影响0人
威玲旺卡
Ai-Reads: Grokking Algorithms.png
书名：《算法图解》（原文书名：《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树，红黑树，堆，伸展树。 - 反向索引（Inverted Indexes），创建搜索引擎
- 傅里叶变换（The Fourier Transform），时域->频域
- 并行算法（Parallel Algorithms）。MapReduce，工具Apache Hadoop，映射函数Map，归并函数Reduce
- 布隆过滤器（Bloom Filter），一种概率型数据结构，可能错报，但不可能漏报
- Hyperloglog，类似布隆过滤器
- SHA算法，应用相同文件/检查密码
- 局部敏感的哈希算法Simhash，SHA局部不敏感
- Diffie-Hellman，RSA密钥，公钥+私钥
- 线性规划（Epilogue），图是线性规划的一个子集
复杂度集合：
- 二分查找：
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月
