《算法图解》整理笔记
一，第一章 算法简介python
1.2 二分查找
二分查找是一种算法，其输入是一个有序的元素列表（必须有序的缘由稍后解释）。若是要查找的元素包含在列表中，二分查找返回其位置；不然返回null。使用二分查找时，每次都排除一半的数字。
通常而言，对于包含n个元素的列表，用二分查找最多须要log2n步，而简单查找最多须要n步。仅当列表是有序的时候，二分查找才管用。
二分法代码实现：web
def binary_search(list, item):
low = 0
high = len(list)—1
while low <= high: #只要范围没有缩小到只包含一个元素，就检查中间的元素
mid = (low + high)
guess = list[mid]
if guess == item: #找到了元素
return mid
if guess > item: #猜的数字大了
high = mid - 1
else: #猜的数字小了
low = mid + 1
return None #没有指定的元素
my_list = [1, 3, 5, 7, 9]
print binary_search(my_list, 3) # => 1
print binary_search(my_list, -1) # => None
1.2.2 运行时间
二分查找的运行时间为对数时间（或log时间）。简单查找的运行时间为线性时间。算法
1.3 大 O表示法
算法的运行时间以不一样的速度增长。
大O表示法指出了算法有多快，大O表示法指的并不是以秒为单位的速度。 大O表示法让你可以比较操做数，它指出了算法运行时间的增速。二分查找须要执行log n次操做，使用大O表示法，O(log n)。简单查找的运行时间为O(n)。大O表示法说的是最糟的情形。数据库
1.3.4 一些常见的大 O 运行时间（“阶指幂对”）
O(log n)，也叫对数时间，这样的算法包括二分查找。
O(n)，也叫线性时间，这样的算法包括简单查找。
O(n * log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
O(n2)，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种很是慢的算法。数组
小结：
1. 算法的速度指的并不是时间，而是操做数的增速。谈论算法的速度时，咱们说的是随着输入的增长，其运行时间将以什么样的速度增长。
2. 算法的运行时间用大O表示法表示。 O(log n)比O(n)快，当须要搜索的元素越多时，前者比后者快得越多。 算法运行时间并不以秒为单位。
3. 算法运行时间是从其增速的角度度量的。缓存
二，第二章 选择排序安全
2.1 内存的工做原理
计算机就像是不少抽屉的集合体，每一个抽屉都有地址。
须要将数据存储到内存时，你请求计算机提供存储空间，计算机给你一个存储地址。须要存储多项数据时，有两种基本方式——数组和链表。
2.2 数组和链表
使用数组意味着全部待办事项在内存中都是相连的（紧靠在一块儿的）。链表中的元素可存储在内存的任何地方。链表的每一个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一块儿。
须要同时读取全部元素时，链表的效率很高：你读取第一个元素，根据其中的地址再读取第二个元素，以此类推。但若是你须要跳跃，链表的效率真的很低。
须要随机地读取元素时，数组的效率很高，由于可迅速找到数组的任何元素。在链表中，元素并不是靠在一块儿的，你没法迅速计算出第五个元素的内存地址，而必须先访问第一个元素以获取第二个元素的地址，再访问第二个元素以获取第三个元素的地址，以此类推，直到访问第五个元素。
2.2.3 术语
元素的位置称为索引。
服务器
2.2.4 在中间插入
须要在中间插入元素时，数组和链表哪一个更好呢？使用链表时，插入元素很简单，只需修改它前面的那个元素指向的地址。数据结构
2.3 选择排序
须要的总时间为 O(n × n)，即O(n2)。
代码实现：app
def findSmallest(arr):
smallest = arr[0]
smallest_index = 0
for i in range(1, len(ar
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr
print selectionSort([5, 3, 6, 2, 10])
第三章 递归
3.2 基线条件和递归条件
编写递归函数时，必须告诉它什么时候中止递归。正由于如此， 每一个递归函数都有两部分：基线条件（ base case）和递归条件（ recursive case） 。递归条件指的是函数调用本身，而基线条件则指的是函数再也不调用本身，从而避免造成无限循环。
代码示例：
def countdown(i):
print i
if i <= 0: #基线条件
return
else: #递归条件
countdown(i-1)
3.3 栈
栈是一种简单的数据结构，栈有两种操做：压入（插入）和弹出（删除并读取）。
每当调用函数时，计算机都像这样将函数调用涉及的全部变量的值存储到内存中。调用另外一个函数时，当前函数暂停并处于未完成状态。该函数的全部变量的值都还在内存中。这个栈用于存储多个函数的变量，被称为调用栈。 调用栈可能很长，这将占用大量的内存。全部函数调用都进入调用栈。
第四章 快速排序
4.1 分而治之
D&C算法包括两个步骤：
(1) 找出基线条件，这种条件必须尽量简单。
(2) 不断将问题分解（或者说缩小规模），直到符合基线条件。
D&C的工做原理：
(1) 找出简单的基线条件；
(2) 肯定如何缩小问题的规模，使其符合基线条件。
快速排序的代码：
def quicksort(array):
if len(array) < 2:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
print quicksort([10, 5, 2, 3])
4.3 再谈大 O 表示法
快速排序的独特之处在于，其速度取决于选择的基准值。选择排序，其运行时间为O(n2)，速度很是慢。
合并排序（ merge sort） 的排序算法，其运行时间为O(n log n)。比选择排序快得多！快速排序的状况比较棘手，在最糟状况下，其运行时间为O(n2)。
4.4 小结
D&C将问题逐步分解。使用D&C处理列表时，基线条件极可能是空数组或只包含一个元素的数组。
实现快速排序时，请随机地选择用做基准值的元素。快速排序的平均运行时间为O(n log n)。
大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的缘由所在。比较简单查找和二分查找时，常量几乎可有可无，由于列表很长时， O(log n)的速度比O(n)快得多。
第五章 散列表
运行时间O(n)和O(log n)之间有天壤之别！
1. 散列函数老是将一样的输入映射到相同的索引。
2. 散列函数将不一样的输入映射到不一样的索引。
3. 散列函数知道数组有多大，只返回有效的索引。若是数组包含5个元素，散列函数就不会返回无效索引100。
散列表也使用数组来存储数据，所以其获取元素的速度与数组同样快。
5.2.3 将散列表用做缓存
缓存的工做原理：网站将数据记住，而再也不从新计算。
缓存是一种经常使用的加速方式，全部大型网站都使用缓存，而缓存的数据则存储在散列表中！
散列表适合用于：
1. 模拟映射关系；
2. 防止重复；
3. 缓存/记住数据，以避免服务器再经过处理来生成它们。
5.3 冲突
冲突（ collision） ：给两个键分配的位置相同。
处理冲突的方式不少，最简单的办法以下：若是两个键映射到了同一个位置，就在这个位置存储一个链表。
散列函数很重要，好的散列函数不多致使冲突。
5.4 性能
在平均状况下，散列表执行各类操做的时间都为O(1)。 O(1)被称为常量时间。简单查找的运行时间为线性时间。二分查找的速度更快，所需时间为对数时间。在最糟状况下，散列表全部操做的运行时间都为O(n)——线性时间，这真的很慢。
在平均状况下，散列表的查找（获取给定索引处的值）速度与数组同样快，而插入和删除速度与链表同样快，所以它兼具二者的优势！但在最糟状况下，散列表的各类操做的速度都很慢。
所以，在使用散列表时，避开最糟状况相当重要。为此，须要避免冲突。而要避免冲突，须要有：
较低的填装因子；
良好的散列函数。
第六章 广度优先搜索（ breadth-first search， BFS）
广度优先搜索让你可以找出两样东西之间的最短距离，广度优先搜索是一种用于图的查找算法，可帮助回答两类问题。
第一类问题：从节点A出发，有前往节点B的路径吗？（在你的人际关系网中，有芒果销售商吗？）
第二类问题：从节点A出发，前往节点B的哪条路径最短？（哪一个芒果销售商与你的关系最近？）
使用这种算法将搜遍你的整我的际关系网，直到找到芒果销售商。这就是广度优先搜索算法。
广度优先搜索不只查找从A到B的路径，并且找到的是最短的路径。
6.3.2 队列
队列相似于栈，你不能随机地访问队列中的元素。队列只支持两种操做： 入队和出队。
队列是一种先进先出（ First In First Out， FIFO）的数据结构，而栈是一种后进先出（ Last InFirst Out， LIFO）的数据结构。
运行时间
若是你在你的整我的际关系网中搜索芒果销售商，就意味着你将沿每条边前行（记住，边是从一我的到另外一我的的箭头或链接），所以运行时间至少为O(边数)。
你还使用了一个队列，其中包含要检查的每一个人。将一我的添加到队列须要的时间是固定的，即为O(1)，所以对每一个人都这样作须要的总时间为O(人数)。因此，广度优先搜索的运行时间为O(人数 + 边数)，这一般写做O(V + E)，其中V为顶点（ vertice）数， E为边数。
你须要按加入顺序检查搜索列表中的人，不然找到的就不是最短路径，所以搜索列表必须是队列。
第七章 狄克斯特拉算法
应用场景：路由协议选路
广度优先搜索，它找出的是段数最少的路径，狄克斯特拉算法（ Dijkstra’s algorithm）找的是最快的路径。广度优先搜索来查找两点之间的最短路径，那时“最短路径”的意思是段数最少。在狄克斯特拉算法中，你给每段都分配了一个数字或权重，所以狄克斯特拉算法找出的是总权重最小的路径。
狄克斯特拉算法包含4个步骤。
(1) 找出“代价最低”的节点，便可在最短期内到达的节点。
(2) 对于该节点的邻居，检查是否有前往它们的更短路径，若是有，就更新其开销。
(3) 重复这个过程，直到对图中的每一个节点都这样作了。
(4) 计算最终路径。
带权重的图称为加权图（ weighted graph），不带权重的图称为非加权图（unweighted graph）。
要计算非加权图中的最短路径，可以使用广度优先搜索。要计算加权图中的最短路径，可以使用狄克斯特拉算法。狄克斯特拉算法只适用于有向无环图。
最短路径指的并不必定是物理距离，也多是让某种度量指标最小。若是有负权边，就不能使用狄克斯特拉算法。由于负权边会致使这种算法无论用。
7.6 小结
1. 广度优先搜索用于在非加权图中查找最短路径。
2. 狄克斯特拉算法用于在加权图中查找最短路径。
3. 仅当权重为正时狄克斯特拉算法才管用。
4. 若是图中包含负权边，请使用贝尔曼-福德算法。
第八章 贪婪算法
贪婪算法的优势——简单易行！贪婪算法很简单：每步都采起最优的作法。用专业术语说，就是你每步都选择局部最优解，最终获得的就是全局最优解。
8.2 背包问题
在有些状况下，完美是优秀的敌人。有时候，你只需找到一个可以大体解决问题的算法，此时贪婪算法正好可派上用场，由于它们实现起来很容易，获得的结果又与正确结果至关接近。
背包问题就是有若干物品，每一个物品有本身的价值和重量。背包有总重量。问题就是怎样将背包装的最大价值。背包问题也分不少种，贪心算法解决的是物品能够拆分的背包问题（就是物品能够分红几份装入）。这个问题用贪心仍是比较好解决的。贪心选择是指所求问题的总体最优解能够经过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。此问题就是将每次的放入当作每一步，要想解决问题，就是将每一步都放入最优解。也就是说，每一次的放入都要放入最佳的选择。讲到这里，就要说一说最佳的选择，每一次的放入的最佳的选择就是每次放入的物品都是剩余的物品中价值最大且质量最小的，这里就要引入一个物品的属性，物品的权重值。物品的权重值就是指物品的价值除以物品的质量。因此，本问题的每一次的最佳选择就是每次都选出权重值最大的物品。
近似算法
在得到精确解须要的时间太长时，可以使用近似算法。判断近似算法优劣的标准以下：
速度有多快；
获得的近似解与最优解的接近程度。
8.4 NP 彻底问题(Non-deterministic Polynomial多项式的不肯定性)
NP彻底问题的简单定义是，以难解著称的问题，如旅行商问题和集合覆盖问题。不少很是聪明的人都认为，根本不可能编写出可快速解决这些问题的算法。
若是可以判断出要解决的问题属于NP彻底问题就行了，这样就不用去寻找完美的解决方案，而是使用近似算法便可。但要判断问题是否是NP彻底问题很难，易于解决的问题和NP彻底问题的差异一般很小。
元素较少时算法的运行速度很是快，但随着元素数量的增长，速度会变得很是慢。
涉及“全部组合”的问题一般是NP彻底问题。
不能将问题分红小问题，必须考虑各类可能的状况。这多是NP彻底问题。
若是问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP彻底问题。
若是问题涉及集合（如广播台集合）且难以解决，它可能就是NP彻底问题。
若是问题可转换为集合覆盖问题或旅行商问题，那它确定是NP彻底问题。
8.5 小结
1. 贪婪算法寻找局部最优解，企图以这种方式得到全局最优解。
2. 对于NP彻底问题，尚未找到快速解决方案。
3. 面临NP彻底问题时，最佳的作法是使用近似算法。
4. 贪婪算法易于实现、运行速度快，是不错的近似算法。
9.1.2 动态规划
动态规划先解决子问题，再逐步解决大问题。
对于背包问题，你先解决小背包（子背包）问题，再逐步解决原来的问题。
每一个动态规划算法都从一个网格开始，网格的各行为商品，各列为不一样容量（ 1～4磅）的背包。全部这些列你都须要，由于它们将帮助你计算子背包的价值。
动态规划功能强大，它可以解决子问题并使用这些答案来解决大问题。 但仅当每一个子问题都是离散的，即不依赖于其余子问题时，动态规划才管用。
- 动态规划可帮助你在给定约束条件下找到最优解。在背包问题中，你必须在背包容量给定的状况下，偷到价值最高的商品。
- 在问题可分解为彼此独立且离散的子问题时，就可以使用动态规划来解决。要设计出动态规划解决方案可能很难，这正是本节要介绍的。下面是一些通用的小贴士。
- 每种动态规划解决方案都涉及网格。
9.3.1 绘制网格
对于前面的背包问题，最终答案老是在最后的单元格中。但对于最长公共子串问题，答案为网格中最大的数字——它可能并不位于最后的单元格中。
9.4 小结
1. 须要在给定约束条件下优化某种指标时，动态规划颇有用。
2. 问题可分解为离散子问题时，可以使用动态规划来解决。
3. 每种动态规划解决方案都涉及网格。
4. 单元格中的值一般就是你要优化的值。
5. 每一个单元格都是一个子问题，所以你须要考虑如何将问题分解为子问题。
6. 没有放之四海皆准的计算动态规划解决方案的公式。
第十章 K最近邻算法
KNN能够用来作两项基本工做——分类和回归：
1. 分类就是编组；
2. 回归就是预测结果（如一个数字）。
余弦类似度（ cosine similarity）
余弦类似度不计算两个矢量的距离，而比较它们的角度。
余弦类似度。余弦类似度被普遍用于协同过滤算法中，尤为是Item-base的协同过滤。
余弦类似度衡量的是两个向量间的夹角大小，经过夹角的余弦值表示结果，假设A向量是（x1, y1），B向量是(x2, y2)，那么两个向量的余弦类似度为：
分子为向量A与向量B的点乘，分母为两者各自的L2相乘，即将全部维度值的平方相加后开方。 余弦类似度的取值为[-1,1]，值越大表示越类似。
10.3.1 OCR
OCR指的是光学字符识别（ optical character recognition），这意味着你可拍摄印刷页面的照片，计算机将自动识别出其中的文字。 通常而言， OCR算法提取线段、点和曲线等特征。
OCR的第一步是查看大量的数字图像并提取特征，这被称为训练（ training）。大多数机器学习算法都包含训练的步骤：要让计算机完成任务，必须先训练它。
10.3.2 建立垃圾邮件过滤器
垃圾邮件过滤器使用一种简单算法——朴素贝叶斯分类器（ Naive Bayes classifier）。
10.4 小结
1. KNN用于分类和回归，须要考虑最近的邻居。
2. 分类就是编组。
3. 回归就是预测结果（如数字）。
4. 特征抽取意味着将物品（如水果或用户）转换为一系列可比较的数字。
5. 可否挑选合适的特征事关KNN算法的成败。
第十一章 接下来如何作
二叉查找树（ binary search tree）
在二叉查找树中查找节点时，平均运行时间为O(log n)，但在最糟的状况下所需时间为O(n)；而在有序数组中查找时，即使是在最糟状况下所需的时间也只有O(log n)，所以你可能认为有序数组比二叉查找树更佳。然而，二叉查找树的插入和删除操做的速度要快得多。
二叉查找树也存在一些缺点，例如，不能随机访问，在二叉查找树处于平衡状态时，平均访问时间也为O(log n)。
11.2 反向索引
一个散列表，将单词映射到包含它的页面。这种数据结构被称为反向索引（ inverted index），经常使用于建立搜索引擎。
11.4 并行算法
并行算法设计起来很难，要确保它们可以正确地工做并实现指望的速度提高也很难。有一点是肯定的，那就是速度的提高并不是线性的，所以即使你的笔记本电脑装备了两个而不是一个内核，算法的速度也不可能提升一倍，其中的缘由有两个。
并行性管理开销。假设你要对一个包含1000个元素的数组进行排序，如何在两个内核之间分配这项任务呢？若是让每一个内核对其中500个元素进行排序，再将两个排好序的数组合并成一个有序数组，那么合并也是须要时间的。
负载均衡。假设你须要完成10个任务，所以你给每一个内核都分配5个任务。但分配给内核A的任务都很容易， 10秒钟就完成了，而分配给内核B的任务都很难， 1分钟才完成。这意味着有那么50秒，内核B在忙死忙活，而内核A却闲得很！你如何均匀地分配工做，让两个内核都同样忙呢？
11.5 MapReduce
MapReduce是一种流行的分布式算法，你可经过流行的开源工具Apache Hadoop来使用它。分布式算法很是适合用于在短期内完成海量工做，其中的MapReduce基于两个简单的理念：映射（ map）函数和归并（ reduce）函数。
11.5.2 映射函数
映射函数很简单，它接受一个数组，并对其中的每一个元素执行一样的处理。
11.5.3 归并函数
归并函数可能使人迷惑，其理念是将不少项归并为一项。映射是将一个数组转换为另外一个数组。
MapReduce使用这两个简单概念在多台计算机上执行数据查询。数据集很大，包含数十亿行时，使用MapReduce只需几分钟就可得到查询结果，而传统数据库可能要耗费数小时。
11.6 布隆过滤器和 HyperLogLog
布隆过滤器是一种几率型数据结构，布隆过滤器的优势在于占用的存储空间不多。使用散列表时，必须存储Google搜集过的全部URL，但使用布隆过滤器时不用这样作。布隆过滤器很是适合用于不要求答案绝对准确的状况，前面全部的示例都是这样的。
HyperLogLog是一种相似于布隆过滤器的算法。
HyperLogLog近似地计算集合中不一样的元素数，与布隆过滤器同样，它不能给出准确的答案，但也八九不离十，而占用的内存空间却少得多。
面临海量数据且只要求答案八九不离十时，可考虑使用几率型算法！
11.7 SHA 算法
另外一种散列函数是安全散列算法（ secure hash algorithm， SHA）函数。给定一个字符串， SHA返回其散列值。
SHA是一个散列函数，它生成一个散列值——一个较短的字符串。用于建立散列表的散列函数根据字符串生成数组索引，而SHA根据字符串生成另外一个字符串。对于每一个不一样的字符串， SHA生成的散列值都不一样。
你可以使用SHA来判断两个文件是否相同，这在比较超大型文件时颇有用。
斐波那契数列
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：一、一、二、三、五、八、1三、2一、3四、……在数学上，斐波纳契数列以以下被以递归的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。
递归方式实现斐波那契数列 前n项:
# 递归方式实现 生成前20项
lis =[]
for i in range(20):
if i ==0 or i ==1:#第1,2项 都为1
lis.append(1)
else:
lis.append(lis[i-2]+lis[i-1])#从第3项开始每项值为前两项值之和
print(lis)
#递归函数实现
def Fibonacci_function_tool(n):
if n <= 0:
return 0
elif n == 1:
return 1
else:
return Fibonacci_function_tool(n - 1) + Fibonacci_function_tool(n - 2)
def Fibonacci_function(n):
result_list = []
for i in range(1, n + 1): result_list.append(Fibonacci_function_tool(i))
return result_list