算法图解
【美】Aditya Bhargava
关于本书
www.manning.com/books/grokking-algorithms
https://github.com/egonschiele/grokking_algorithms
1.2.1 更佳的查找方式
一般而言，对于包含n个元素的列表，用二分查找最多需要log2n步，而简单查找最多需要n步。
1.3.4 一些常见的大O运行时间
下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。
O(log^n)，也叫对数时间，这样的算法包括二分查找。
O(n)，也叫线性时间，这样的算法包括简单查找。
O(n*log^n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
O(n^2)，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。
3.1 递归
Leigh Caldwell在Stack Overflow上说的一句话：“如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。”
3.3.2 递归调用栈
使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况下，你有两种选择。
重新编写代码，转而使用循环。
使用尾递归
第4章 快速排序
学习快速排序——一种常用的优雅的排序算法。快速排序使用分而治之的策略。
4.2 快速排序
语言标准库中的函数qsort实现的就是快速排序
4.3 再谈大O表示法
选择排序，其运行时间为O(n2)，速度非常慢。
还有一种名为合并排序（merge sort）的排序算法，其运行时间为O(n logn)，比选择排序快得多！快速排序的情况比较棘手，在最糟情况下，其运行时间为O(n2)。
与选择排序一样慢！但这是最糟情况。在平均情况下，快速排序的运行时间为O(n logn)。
5.3 冲突
散列函数总是将不同的键映射到数组的不同位置。
处理冲突的方式很多，最简单的办法如下：如果两个键映射到了同一个位置，就在这个位置存储一个链表。
5.4 性能
避免冲突，需要有：
较低的填装因子；
良好的散列函数。
第6章 广度优先搜索
广度优先搜索让你能够找出两样东西之间的最短距离
6.3.2 队列
队列是一种先进先出（First In First Out，FIFO）的数据结构，而栈是一种后进先出（Last In First Out，LIFO）的数据结构。
第7章 狄克斯特拉算法
介绍狄克斯特拉算法，让你能够找出加权图中前往X的最短路径。
介绍图中的环，它导致狄克斯特拉算法不管用。
7.2 术语
狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重（weight）。
要计算非加权图中的最短路径，可使用广度优先搜索。要计算加权图中的最短路径，可使用狄克斯特拉算法
7.4 负权边
如果有负权边，就不能使用狄克斯特拉算法
在包含负权边的图中，要找出最短路径，可使用另一种算法——贝尔曼-福德算法（Bellman-Ford algorithm）。
7.5 实现
节点的所有邻居都存储在散列表中。
一个散列表来存储每个节点的开销。
节点的开销指的是从起点出发前往该节点需要多长时间。
还需要一个存储父节点的散列表
需要一个数组，用于记录处理过的节点，因为对于同一个节点，你不用处理多次。
第8章 贪婪算法
学习贪婪策略
8.1 教室调度问题
贪婪算法很简单：每步都采取最优的做法
第9章 动态规划
学习动态规划，这是一种解决棘手问题的方法，它将问题分成小问题，并先着手解决这些小问题。
9.1.2 动态规划
动态规划先解决子问题，再逐步解决大问题。
9.4 小结
需要在给定约束条件下优化某种指标时，动态规划很有用。
问题可分解为离散子问题时，可使用动态规划来解决。
每种动态规划解决方案都涉及网格。
单元格中的值通常就是你要优化的值。
每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题。
没有放之四海皆准的计算动态规划解决方案的公式。
第10章 K最近邻算法
K最近邻算法创建分类系统
10.2.1 特征抽取
要计算两点的距离，可使用毕达哥拉斯公式。
10.2.2 回归
使用KNN来做两项基本工作——分类和回归：
分类就是编组；
回归就是预测结果（如一个数字）。
余弦相似度
前面计算两位用户的距离时，使用的都是距离公式。
余弦相似度不计算两个矢量的距离，而比较它们的角度，因此更适合处理前面所说的情况。本书不讨论余弦相似度，但如果你要使用KNN，就一定要研究研究它！
10.3.2 创建垃圾邮件过滤器
垃圾邮件过滤器使用一种简单算法——朴素贝叶斯分类器（Naive Bayes classifier）
10.4 小结
KNN用于分类和回归，需要考虑最近的邻居。
分类就是编组。
回归就是预测结果（如数字）。
特征抽取意味着将物品（如水果或用户）转换为一系列可比较的数字。
能否挑选合适的特征事关KNN算法的成败。
如果考虑的邻居太少，结果很可能存在偏差。一个不错的经验规则是：如果有N位用户，应考虑sqrt(N)个邻居。
11.1 树
二叉查找树
对于其中的每个节点，左子节点的值都比它小，而右子节点的值都比它大。
也有一些处于平衡状态的特殊二叉查找树，如红黑树。
B树是一种特殊的二叉树，数据库常用它来存储数据。
请研究如下数据结构：B树，红黑树，堆，伸展树。
11.3 傅里叶变换
绝妙、优雅且应用广泛的算法少之又少，傅里叶变换算是一个。
傅里叶变换非常适合用于处理信号，可使用它来压缩音乐。
11.4 并行算法
并行算法
在最佳情况下，排序算法的速度大致为O(n logn)。众所周知，对数组进行排序时，除非使用并行算法，否则运行时间不可能为O(n)！对数组进行排序时，快速排序的并行版本所需的时间为O(n)。
11.5 MapReduce
有一种特殊的并行算法正越来越流行，它就是分布式算法。在并行算法只需两到四个内核时，完全可以在笔记本电脑上运行它，但如果需要数百个内核呢？在这种情况下，可让算法在多台计算机上运行。MapReduce是一种流行的分布式算法，你可通过流行的开源工具Apache Hadoop来使用它。
11.5.1 分布式算法为何很有用
分布式算法非常适合用于在短时间内完成海量工作，其中的MapReduce基于两个简单的理念：映射（map）函数和归并（reduce）函数。
11.5.3 归并函数
映射是将一个数组转换为另一个数组。
而归并是将一个数组转换为一个元素。
11.6 布隆过滤器和HyperLogLog
布隆过滤器和HyperLogLog
11.6.1 布隆过滤器
布隆过滤器提供了解决之道。布隆过滤器是一种概率型数据结构，它提供的答案有可能不对，但很可能是正确的
11.6.2 HyperLogLog
HyperLogLog是一种类似于布隆过滤器的算法
面临海量数据且只要求答案八九不离十时，可考虑使用概率型算法！
11.7 SHA算法
SHA算法
11.7.1 比较文件
另一种散列函数是安全散列算法（secure hash algorithm，SHA）函数。给定一个字符串，SHA返回其散列值。
11.7.2 检查密码
当前，最安全的密码散列函数是bcrypt，
11.8 局部敏感的散列算法
希望散列函数是局部敏感的。在这种情况下，可使用Simhash
如果你对字符串做细微的修改，Simhash生成的散列值也只存在细微的差别。这让你能够通过比较散列值来判断两个字符串的相似程度，这很有用！
11.9 Diffie-Hellman密钥交换
这里有必要提一提Diffie-Hellman算法，它以优雅的方式解决了一个古老的问题：如何对消息进行加密，以便只有收件人才能看懂呢？
Diffie-Hellman使用两个密钥：公钥和私钥
Diffie-Hellman算法及其替代者RSA依然被广泛使用
11.10 线性规划
线性规划用于在给定约束条件下最大限度地改善指定的指标
线性规划使用Simplex算法
参考
http://www.cnblogs.com/OctoptusLian/p/9026319.html?dt_platform=other&dt_dapp=1
