《算法图解》各章学习

1、算法简介

二分法

二分查找法，用于有序元素列表，以一半为界分开，确定元素在哪一部分，继续前述操作。速度最快，包含n个元素时为 $ \log_2 n$

大O表示法

用于表示算法的速度，O()。真正的速度需要乘以时间常数c，一般分析时不考虑。

2、选择排序

数组

数组在内存中储存的信息是连在一起的，方便读取操作。

链表

链表的信息在内存中是无序的，下一个内存地址由上一个内存中的信息给出，方便插入和删除操作。

选择排序

不断遍历整个无序列表，将元素有序排列出来，速度为O(n×n)或O(n²)
(大O表示法省略常数)

3、递归

递归：自己调用自己的函数。
递归函数条件：基线条件和递归条件，递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己（例如设置调用次数），从而避免形成无限循环。

栈（stack）

调用栈有压入和弹出两个操作，都只操作最上面的内存块，而不是压入底部的内存。所有函数调用都进入调用栈。
递归时函数不断将同名不同参考值的函数压入调用栈，使用时弹出。因此调用栈可能很长，这将占用大量的内存。

4、快速排序

D&C算法思想：找出简单的基线条件，)确定如何缩小问题的规模，使其符合基线条件。
因此处理列表时基线条件很可能是空数组或只包含一个元素的数组。

快速排序

方法：首先在数组中选择一个元素作为基准值。接下来，找出比基准值小的元素以及比基准值大的元素各自分为两个子数组。对子数组进行基准值→子数组的递归，直到子数组中只剩1个或没有元素停止（基线条件）。最后左边的数组 + 基准值 + 右边的数组合并为排序结果。
算法速度：实现快速排序时，随机地选择用作基准值的元素。快速排序的平均运行时间为 $O(nlog⁡n)O(n\log n)$ ，也是最佳情况下的时间，最坏情况（取到了数组中最大或最小的基准值）运行时间是O（n²）。

5、散列表

散列函数

数据的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应，因此散列函数可以直接确定元素的储存位置。

散列表(hash table)

使用散列函数和数组创建了一种被称为散列表 (hash table)的数据结构。Python提供的散列表实现为字典，使用函数dict()来创建散列表。
用途：除了快速查找数据以外，还可以用于映射关系，缓存数据（例如，在Web服务器上），防止重复等。
冲突：在散列表中，不同的关键字值对应到同一个存储位置的现象。
处理方法：(1)在冲突的位置储存一个链表，极端情况链表很长造成散列表的速度很慢。(2)降低填装因子，使每个关键字都有自己的储存位置，一旦填装因子超过0.7，就该加长散列表的长度。(3)良好的散列函数让数组中的值呈均匀分布。
性能：散列表的查找、插入、删除在理想情况下均为常量时间O(1).在冲突很多的情况下，速度变慢，最差情况性能变化为线性时间O(n)。

6、广度优先搜索

图

图由节点和边组成。使用图来创建问题模型，使用广度优先搜索解决问题。
广度优先搜索可回答两类问题，从节点A出发，有前往节点B的路径吗；从节点A出发，前往节点B的哪条路径最短。

队列

队列类似于栈，你不能随机地访问队列中的元素。队列是一种先进先出 （First In First Out，FIFO）的数据结构，而栈是一种后进先出的数据结构。队列只支持两种操作：入队和出队。
在Python中，可使用函数deque()来创建一个双端队列。

广度优先搜索算法

(1)建立图模型，在这里，要将节点映射到其所有邻居，如graph["you"] = ["alice", "bob", "claire"]以此类推；
(2)创建队列，将所有一度关系对象加入队列，取出队列的第一个元素并检查，符合要求结束，不符合则将这个节点的一度关系对象加入队列；
(3)继续按顺序检查队列（否则找到的就不是最短路径），直到队列为空或找到需要搜索的对象。检查队列时同时将检查过的对象放入数组中，防止二次检查浪费时间。

def search(name):search_queue = deque()search_queue += graph[name]searched = [] ←------------------------------这个数组用于记录检查过的人while search_queue:person = search_queue.popleft()if person not in searched: ←----------仅当这个人没检查过时才检查if person_is_seller(person):print person + " is a mango seller!"return Trueelse:search_queue += graph[person]searched.append(person) ←------将这个人标记为检查过return False

性能：总运行时间 $O (V + E)$ ，其中V为顶点（vertice）数，E为边数。

7、狄克斯特拉算法

广度优先的算法来查找两点之间的最短距离，那时的“最短距离”是指路径最少。在狄克斯特拉算法中，你给每段都分配了一个数字或权重，因此狄克斯特拉算法找出的是总权重最小的路径。

狄克斯特拉算法

(1) 找出最便宜的节点，即可在最短时间内前往的节点。
(2) 对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。
(3) 重复这个过程，直到对图中的每个节点都这样做了。
(4) 计算最终路径。
注意：仅当权重为正时使用狄克斯特拉算法；如果图中包含负权边，则使用贝尔曼-福德算法。

def dijkstra():       //狄克斯特拉算法代码node = find_lowest_cost_node(costs) ←------在未处理的节点中找出开销最小的节点while node is not None: ←------这个while循环在所有节点都被处理过后结束cost = costs[node]neighbors = graph[node]for n in neighbors.keys(): ←------遍历当前节点的所有邻居new_cost = cost + neighbors[n]if costs[n] > new_cost: ←------如果经当前节点前往该邻居更近，costs[n] = new_cost ←------就更新该邻居的开销parents[n] = node ←------同时将该邻居的父节点设置为当前节点processed.append(node) ←------将当前节点标记为处理过node = find_lowest_cost_node(costs) ←------找出接下来要处理的节点，并循环

def find_lowest_cost_node(costs):      //找出开销最低的节点代码lowest_cost = float("inf")lowest_cost_node = Nonefor node in costs: ←------遍历所有的节点cost = costs[node]if cost < lowest_cost and node not in processed: ←------如果当前节点的开销更低且未处理过，lowest_cost = cost ←------就将其视为开销最低的节点lowest_cost_node = nodereturn lowest_cost_node

8、贪婪算法

对于NP完全问题来说，目前没有算法能够快速找到问题的最优解，最佳的做法是使用近似算法（贪婪算法）。
NP完全问题特征：元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢；不能将问题分成小问题，必须考虑各种可能的情况；问题涉及序列、集合、组合且难以解决。
NP完全问题更加科学的定义关于多项式时间，此处不展开。

贪婪算法

**贪婪算法：**在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。

贪婪算法并没有固定的算法解决框架，算法的关键是贪婪策略的选择，根据不同的问题选择不同的策略。

必须注意的是策略的选择必须具备无后效性，即某个状态的选择不会影响到之前的状态，只与当前状态有关，所以对采用的贪婪的策略一定要仔细分析其是否满足无后效性。

前面介绍的最短路径问题，广度优先、狄克斯特拉都属于贪婪算法，只是在其问题策略的选择上，刚好可以得到最优解。

9、动态规划

动态规划：在约束条件下，将问题划分为若干子问题并对其求出最优解，同时将子问题的答案存储起来，以减少重复计算相同子问题的次数，最终求出问题最优解的算法思想。
书中的例子背包问题，把装4磅的背包分解为装1、2、3、4磅的包，把每一步的答案储存起来，最后的答案取决于前一步答案。这种方法降低了算法的时间复杂度。

应用动态规划（三步走）

1、建立状态转移方程：建立如斐波那契数列的递推方程作为状态转移方程，如 $f (n) = f (n - 1) + f (n - 2)$
**2、缓存并复用以往结果：**记录下 $f (1)$ 、 $f (2)$ … $f (99)$ ，则 $f (100)$ 只需复用前面的子结果，进行一次加法运算即可得到结果。
**3、按顺序从小往大算：**这里的“小”和“大”对应的是问题的规模，从小到大一步步递推出最终的结果。
**例子：**斐波那契数列计算
简单递归：时间复杂度$ O（2^{n}）$

动态规划：线性规划通过缓存与复用机制将计算规模缩小到红色部分，时间复杂度$ O（n）$

10、K最近邻算法

特征提取、分类、回归，分类时主义选择合适的公式。（模式识别有详细讲解）

11、其他算法

ⅰ.二叉查找树

对于其中的每个节点，左子节点的值都比它小，而右子节点的值都比它大。
在二叉查找树中查找节点时（类似有序数组二分查找操作），平均运行时间为$ O(\log n)$ （二分查找操作同样为这个），但在最糟的情况下所需时间为$ O(n) $；插入和删除操作平均运行时间同样为$ O(\log n)$。
二叉查找树不能随机访问，如果树处于不平衡状态（左右的节点数显著不等）会导致性能不佳。

ⅱ.反向索引

ⅲ.傅里叶变换

处理信号。
例如傅里叶变换能够准确地指出各个音符对整个歌曲的贡献，让你能够将不重要的音符删除。这就是MP3格式的工作原理！

ⅳ.并行算法

排序算法的速度大致为$ O(n\log n) $，使用并行算法快速排序的所需的时间可以减少为$ O(n)$。由于并行性管理开销以及负载需要均衡的原因，并行算法提升速度并不是线性的。

Ⅴ.MapReduce

分布式算法MapReduce基于两个简单的理念：映射（map）函数和归并（reduce）函数。

映射函数

接受一个数组，并对其中的每个元素执行同样的处理。相当于将多个相同任务映射到多个服务器上去处理。

归并函数

将很多项归并为一项，例如吧所有服务器运算得到的结果相加。

ⅵ.布隆过滤器和HyperLogLog

概率型数据结构，不能给出准确的答案，但也较为接近，而占用的内存空间比起散列表却小得多。

ⅶ.SHA算法

安全散列算法（SHA）函数，给定一个字符串，SHA返回其散列值。这种散列算法是单向的。你可根据字符串计算出散列值，但不能更具散列值计算出字符串。用于比较大型文件，检查密码等。

ⅷ.局部敏感的散列算法

SHA重要特征局部不敏感，修改其中的一个字符，再计算其散列值，结果将截然不同。
Simhash散列函数是局部敏感的，对字符串做细微的修改，Simhash生成的散
列值也只存在细微的差别，这能够通过比较散列值来判断两个字符串的相似程度。

Ⅸ.Diffie-Hellman密钥交换

Diffie-Hellman使用两个密钥：公钥和私钥。发送消息时使用公钥对其进行加密。加密后的消息只有使用私钥才能解密。