©2016-2024 Matools All rights reserved,
粤ICP备17059708号
一，第一章 算法简介
1.2 二分查找
二分查找是一种算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。使用二分查找时，每次都排除一半的数字。
一般而言，对于包含n个元素的列表，用二分查找最多需要log2n步，而简单查找最多需要n步。仅当列表是有序的时候，二分查找才管用。
二分法代码实现：
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)。
代码实现：
def findSmallest(arr): smallest = arr[0] smallest_index = 0 for i in range(1,
len(arif arr[i] < smallest: smallest = arr[i] smallest_index = i return
smallest_indexdef 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 = [ifor 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)，那么两个向量的余弦相似度为：
cosθ=A⋅B||A||∗||B||=x1y1+x2y2(√x21+y21)∗(√x22+y22)cosθ=A⋅B||A||∗||B||=x1y1+x2y2
(x12+y12)∗(x22+y22)
分子为向量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、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：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
热门工具 换一换