- 前言知识
- 第一章，算法简介
- 第二章，选择排序
- 第三章，递归
- 第四章，快速排序
- 第五章，散列表
- 第六章，广度优先搜索
- 第七章，迪克斯特拉算法
- 第八章，贪婪(贪心)算法
- 第九章，动态规划
- 第十章，K最近邻算法
- 第十一章 接下来如何做
前言知识
10 大排序算法时间复杂度及空间复杂度如下图：
第一章，算法简介
1.2，二分法查找元素
二分查找是一种算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回 null，使用二分查找时，每次猜测的是中间的数字，从而将余下的数字排除一半。（仅仅当列表是有序的时候，二分查找才管用）
一般而言，对于包含n个元素的列表查找某个元素，使用二分法最多需要 \(log_{2}n\) 步(**时间复杂度为 \(log_{2}n\) **)，简单查找最多需要 n 步。大 O 表示法指出了算法最糟糕情况下的运行时间。二分法实例代码如下：
def binary_search(list, item):
low = 0
high = len(list)-1
while low <= high:
mid = (low + high) // 2
if list[mid] == item:
return mid
elif list[mid] > item:
high = mid - 1
else:
low = mid + 1
return None
if __name__ == "__main__":
print(binary_search([1,2,3,4,6,7], 3)) # 输出 2
1.2.1，特殊的二分查找
有序数组中的目标出现多次，利用二分查找返回在最左边出现的目标值或者是最右边出现的目标值，实例代码如下：
def binary_search2(arr, target, flag="left"):
if not arr:
return None
left = 0
right = len(arr) - 1
while left <= right:
mid = left + (right - left) // 2 # 防止数据过大溢出?
if arr[mid] < target:
left = mid + 1
elif arr[mid] > target:
right = mid -1
else:
if flag == "left":
if mid > 0 and arr[mid-1] == target:
right = mid -1 # 不断向最左边逼近
else:
return mid
elif flag == "right":
if mid + 1 < len(arr) and arr[mid + 1] == target:
left = mid + 1 # 不断向最右边逼近
else:
return mid
return None
if __name__ == "__main__":
print(binary_search2([1,1,1,3,3,3,4], 3, "left")) # 查找最左边出现的目标值, 输出3
print(binary_search2([1,1,1,3,3,3,4,4,4], 3, "right")) # 查找最右边出现的目标值, 输出5
第二章，选择排序
2.1，内存工作原理
在计算机中，存储多项数据时，有两种基本方式－数组和链表。但它们并非适用于所有情形。
2.2.1，链表
链表中的元素可存储在内存的任何地方。
链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。链表结构直观显示如下图所示：
链表的优势在插入元素方面，那数组的优势又是什么呢？
2.2.2，数组
需要随机地读取元素时，数组的效率很高，因为可迅速找到数组的任何元素。在链表中，元素并非靠在一起的，你无法迅速计算出第五个元素的内存 地址，而必须先访问第一个元素以获取第二个元素的地址，再访问第二个元素以获取第三个元素 的地址，以此类推，直到访问第五个元素。
2.2.3，术语
数组的元素带编号，编号从 0 而不是 １ 开始，几乎所有的编程语言都从０开始对数组元素进行编号，比如C/C++的数组结构和Python的列表结构。
元素的位置称为索引。下面是常见数组和链表操作的运行时间.
2.3，选择排序
选择排序时间复杂度\(O(n^{2})\)
def findSmallest(arr):
smallest = arr[0] # 存储最小的值
smallest_index = 0 # 存储最小元素的索引
for i in range(1, len(arr)):
if arr[i] < smallest:
smallest_index = i
smallest = arr[i]
return smallest
# 选择排序法对数组进行排序
def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
arr.remove(smallest)
newArr.append(smallest)
return newArr
# 实例应用
print(selectionSort([5, 3, 6, 100])) # [3, 5, 6, 100]
2.4，小结
- 计算机内存犹如一大堆抽屉。
- 需要存储多个元素时，可使用数组或链表。
- 数组的元素都在一起。
- 链表的元素是分开的，其中每个元素都存储了下一个元素的地址。
- 数组的读取速度很快。
- 链表的插入和删除速度很快.
- 在同一个数组中，所有元素的类型都必须相同（都为int、 double等）。
第三章，递归
学习如何将问题分成基线条件和递归条件，学习如何使用递归算法，递归算法直观上更好理解，步骤简单。
3.2，基线条件和递归条件
编写递归函数时，必须告诉它何时停止，因此，每个递归函数有两个部分：基线条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己，而基线条件则 指的是函数不再调用自己，从而避免形成无限循环。
3.3，栈
栈的定义：栈是一种只能从表的一端存取数据且遵循 "先进后出" 原则的线性存储结构。
调用栈(call stack)
3.3.1，调用栈
计算机在内部使用被称为调用栈的栈。调用另一个函数时，当前函数暂停 并处于未完成状态。该函数的所有变量的值都还在内存中。栈顶的方框指出了当前执行 到了什么地方。
3.3.2，递归调用栈
栈在递归中扮演着重要角色。使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存。每个函数调 用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况 下，你有两种选择。
- 重新编写代码
- 使用尾递归
3.4，小结
- 递归值的是调用自己的函数
- 每个递归函数都有两个条件：基线条件和递归条件
- 栈有两种操作：压如和弹出
- 所有函数调用都进入调用栈
- 调用栈可能很长，这将占用大量内存
第四章，快速排序
快速排序使用分而治之的策略，分而治之是我们学习的第一种通用的问题解决办法。
分而治之(divide and conquer，D&C)-一种著名的递归式问题解决办法。
4.1，分而治之
D&C算法是递归的。使用D&C解决问题的过程包括两个步骤：
- 找出基线条件，这种条件必须尽可能简单。
- 不断将问题分解（或者说缩小规模），直到符合基线条件。
D&C并非可直接用于解决问题的算法，而是一种解决问题的思路。
4.2 快速排序
C语言标准库中的函数qsort实现的就是快速排序。快速排序也是用了D&C思想。
对数组进行快速排序，步骤如下：
- 随机选择一个基准值；
- 将数组分成两个子数组：小于基准值的元素和大于基准值额元素；
- 对这两个子数组进行排序。
在平均情况下，快速排序时间复杂度\(O(nlogn)\)。快速排序代码如下：
def quicksort(array):
if len(array) < 2:
# 基线条件：为空或只包含一个元素的数组是“有序”的
return array
else:
# 递归条件
pivot = array[0]
less = [x for x in array[1:] if x <= pivot]
greater = [x for x in array[1:] if x > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([4, 90, 0, 2, 17, 79, 12])) # [0, 2, 4, 12, 17, 79, 90]
上面的代码空间复杂度很大，真正的快排是原地排序，空间复杂度为O(1)，代码如下：
# _*_ coding:utf-8 _*_
def quick_sort(L):
return q_sort(L, 0, len(L)-1)
def q_sort(L, left, right):
if left < right:
pivot = Partition(L, left, right)
q_sort(L, left, pivot-1)
q_sort(L, pivot+1, right)
return L
def Partition(L, left, right):
pivotkey = L[left]
while left < right:
while left < right and L[right] >= pivotkey:
right -= 1
L[left] = L[right]
while left < right and L[left] <= pivotkey:
left += 1
L[right] = L[left] # 遇到比基准大的数, 则覆盖在之前尾部指针的位置
L[left] = pivotkey
return left
if __name__ == "__main__":
L = [5, 9, 1, 1, 11, 6, 7, 2, 4]
print(quick_sort(L))
4.3 再谈大Ｏ表示法
快速排序的独特之处在于，其速度取决于选择的基准值。在讨论快速排序的运行时间前，我 们再来看看最常见的大O运行时间。
- 选择排序，其运行时间为 \(O(n^2)\)，速度非常慢。
- 还有一种名为合并排序（merge sort）的排序算法，其运行时间为 \(O(nlogn)\)，比选择排序快得多！
- 快速排序的情况比较棘手，在最糟情况下，其运行时间为 \(O(n^2)\)。与选择排序一样慢！但这是最糟情况。在平均情况下，快速排序的运行时间为 \(O(nlogn)\)。
由对数的换底公式，\(log_a n\) 和 \(log_b n\) 只有一个常数因子不同，这个因子在大O记法中被丢弃。因此记作\(O(log n)\)，而不论对数的底是多少，是对数时间算法的标准记法。
4.4，小结
- D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元 素的数组。
- 实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)。
- 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。
- 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时， O(log n)的速度比O(n) 快得多。
第五章，散列表
数组和链表结构可以用以查找，栈不行。散列表也叫哈希表(Hash table)，散列表有些类似 Python 中的字典 dict 结构。散列表可用以：
- 模拟映射关系；
- 防止重复；
- 缓冲/记住数据，以免服务器再通过处理来生成它们。
5.3，冲突
给两个键分配的位置相同，这被称为冲突（collision）。处理冲突最简单的办法就是：如果两个键映射到了同一个位置，就在这个位置存储一个链表。
5.4，性能
散列表，数组，链表的查找、插入删除元素的时间复杂度，如下表所示：
在平均情况下，散列表的查找（获取给定索引处的值）速度与数组一样快，而插入和删除速 度与链表一样快，因此它兼具两者的优点！但在最糟情况下，散列表的各种操作的速度都很慢。 因此，在使用散列表时，避开最糟情况至关重要。为此，需要避免冲突。而要避免冲突，需要有：
- 较低的填装因子；
- 良好的散列函数。
5.5，小结
散列表是一种功能强大的数据结构，其操作速度快，还能让你以不同的方式建立数据模型。 你可能很快会发现自己经常在使用它。
- 你可以结合散列函数和数组来创建散列表。
- 冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。
- 散列表的查找、插入和删除速度都非常快。
- 散列表适合用于模拟映射关系。
- 一旦填装因子超过0.7，就该调整散列表的长度。
- 散列表可用于缓存数据（例如，在Web服务器上）。
- 散列表非常适合用于防止重复。
第六章，广度优先搜索
图算法：广度优先搜索（breadth-first search, BFS）算法
广度优先搜索让你能够找出两样东西之间的最短距离，不过最短距离的含义有很多！使用广度优先搜索可以：
- 编写国际跳棋AI，计算最少走多少步就可获胜；
- 编写拼写检查器，计算最少编辑多少个地方就可将错拼的单词改成正确的单词，如将 READED改为READER需要编辑一个地方；
- 根据你的人际关系网络找到关系最近的医生。
解决最短路径问题的算法被称为广度有限算法，一般步骤为：
- 使用图来建立问题模型。
- 使用广度优先搜索解决问题。
6.1，图是什么
图由节点（node）和边（edge）组成。
6.2，广度优先搜索
在广度优先搜索的执行过程中，搜索范围从起点开始逐渐向外延伸，即先检查一度关系，再检查二度关系。
6.3，栈与队列
- 栈：后进先出（Last In First Out，LIFO）的数据结构
- 队列：先进先出（First In First Out，FIFO）的数据结构，支持入队和出对操作。
6.4，代码实现图结构
图中每个节点都与相邻节点相连，散列表结构可以表示这种关系。
图分为有向图（directed graph）和无向图（undirected graph），有向图关系是单向的，无向图没有箭头，直接相连的节点互为邻居。对从自己出发有指向他人的箭头，则有邻居。
6.4.1 运行时间
如果你在你的整个人际关系网中搜索芒果销售商，就意味着你将沿每条边前行（记住，边是从一个人到另一个人的箭头或连接），因此运行时间至少为 \(O(边数)\)。你还使用了一个队列，其中包含要检查的每个人。将一个人添加到队列需要的时间是固定的，即为 \(O(1)\)，因此对每个人都这样做需要的总时间为 \(O(人数)\)。所以，广度优先搜索的运行时间为 \(O(人数 + 边数)\)，这通常写作 \(O(V + E)\)，其中 \(V\) 为顶点（ vertice）数， \(E\) 为边数。
第七章，迪克斯特拉算法
7.1，使用迪克斯特拉算法
迪克斯特拉算法能够找出加权图中前往X的最短路径。对于寻找耗时最少的路径，迪克斯特拉算法包含４个步骤：
- 找出“最便宜”的节点，即可在最短时间内到达的节点。
- 更新该节点的邻居的开销，其含义将稍后介绍。
- 重复这个过程，直到对图中的每个节点都这样做了。
- 计算最终路径。
每个节点都有开销。开销指的是从起点前往该节点需要多长时间。
7.2，术语
- 带权重的图称为加权图（ weighted graph），不带权重的图称为非加权图（ unweighted graph）。
- 要计算非加权图中的最短路径，可使用广度优先搜索。要计算加权图中的最短路径，可使用狄克斯特拉算法。
- 在无向图中，每条边都是一个环。狄克斯特拉算法只适用于有向无环图（ directed acyclic graph， DAG）。
图可能有环，所谓环，是指由一个节点出发，走一圈后可以又回到原节点，如下图所示：
7.3，负权边
因此， 不能将狄克斯特拉算法用于包含负权边的图。在包含负权边的图中，要找出最短路径，可使用另一种算法——贝尔曼福德算法（ Bellman-Ford algorithm）。
7.4，编程实现狄克斯特拉算法
以下图为例，编程实现耗时最短的路径。
代码如下：
# 为了实现带权图，可使用散列表，散列表用Python字典实现
graph = {}
# 存储起始节点邻居和前往邻居的开销
graph['start'] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
print(graph["start"].keys())
# 添加其他节点及其邻居
graph["a"] = {}
graph["a"]["fin"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
# 终点没有任何邻居
graph['fin'] = {}
# 创建存储每个节点开销的开销表
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
# 创建存储父节点的散列表
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
# 创建一个数组，用于记录处理过的节点
processed = []
# 找出开销最低的节点
def find_lowest_cost_node(costs):
lowest_cost = float("inf")
lowest_cost_node = None
for node in costs:
cost = costs[node]
if cost < lowest_cost and node not in processed:
lowest_cost = cost
lowest_cost_node = node
return lowest_cost_node
# 在未处理的节点中找出开销最小的节点
node = find_lowest_cost_node(costs)
while node is not None:
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)
print("Cost from the start to each node:")
print(costs)
7.5，小结
- 广度优先搜索用于在非加权图中查找最短路径。
- 狄克斯特拉算法用于在加权图中查找最短路径。
- 仅当权重为正时狄克斯特拉算法才管用。
- 如果图中包含负权边，请使用贝尔曼福德算法。
第八章，贪婪(贪心)算法
贪婪算法思想很简单：每步都采取最优的做法，专业术语说，就是每步都选择局部最优解，最终得到的就是全局最优解。
8.1，教室调度问题
根据给定课表，尽可能将更多的课程安排在某间教室。解决办法：贪婪算法可找到最优解。
8.2，背包问题
背包重量有限，根据策略使得装入背包的物品价值最高。
在这里， 贪婪策略显然不能获得最优解，但非常接近。在有些情况下，完美是优秀的敌人。有时候，你只需找到一个能够大致解决问题的算法，此时贪婪算法正好可派上用场，因为它们实现起来很容易，得到的结果又与正确结果相当接近。
8.3，集合覆盖问题
每个广播台都覆盖特定区域的州，找出覆盖全美50个州的最小广播集合。
贪婪算法解决这个问题，当广播台数量过多，算法所耗费的时间将激增。
8.3.1，近似算法
集合覆盖问题举例：每个广播台都覆盖特定区域的州，找出覆盖全美50个州的最小广播集合。贪婪算法可以解决这个问题，当广播台数量过多，算法所耗费的时间将激增。
- 选出这样一个广播台，即它覆盖了最多的未覆盖州。即便这个广播台覆盖了一些已覆盖的州，也没有关系。
- 重复第一步，直到覆盖了所有的州。
这是一种近似算法（ approximation algorithm） 。在获得精确解需要的时间太长时，可使用近似算法。判断近似算法优劣的标准如下：
- 速度有多快；
- 得到的近似解与最优解的接近程度。
代码实例：
"""
准备工作
"""
# 创建一个列表，包含要覆盖的州
states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])
# 广播台清单
stations = {}
stations["kone"] = set(["id", "nv", "ut"])
stations["ktwo"] = set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "ca"])
stations["kfour"] = set(["nv", "ut"])
stations["kfive"] = set(["ca", "az"])
# 定义一个集合存储最终选择的广播台
final_stations = set()
"""
计算答案
"""
best_station = None
while states_needed:
best_station = None
states_covered = set()
for station, states in stations.items():
covered = states_needed & states
if len(covered) > len(states_covered):
best_station = station
states_covered = covered
states_needed -= states_covered
final_stations.add(best_station)
print(final_stations)
程序输出如下：
{'kone', 'ktwo', 'kthree', 'kfive'}
贪心算法的实质是每次选出当前的最优解，不管整体，是基于一定假设下的最优解。
8.4，NP完全问题
旅行商问题和集合覆盖问题有一些共同之处：你需要计算所有的解，并从中选出最小/最短的那个。这两个问题都属于NP完全问题。NP完全问题的简单定义是，以难解著称的问题，如旅行商问题和集合覆盖问题。很多非常聪明的人都认为，根本不可能编写出可快速解决这些问题的算法。
8.4.1，如何识别NP完全问题
NP 完全问题无处不在！如果能够判断出要解决的问题属于 NP 完全问题就好了，这样就不用 去寻找完美的解决方案，而是使用近似算法即可。但要判断问题是不是NP完全问题很难，易于解决的问题和 NP 完全问题的差别通常很小。
但如果要找出经由指定几个点的的最短路径，就是旅行商问题——NP完全问题。简言之，没办法判断问题是不是 NP 完全问题，但还是有一些蛛丝马迹可循的。
- 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
- 涉及“所有组合”的问题通常是NP完全问题。
- 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。
- 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。
- 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。
- 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。
8.5，小结
- 贪婪算法寻找局部最优解，企图以这种方式获得全局最优解。
- 对于NP完全问题，还没有找到快速解决方案。
- 面临NP完全问题时，最佳的做法是使用近似算法。
- 贪婪算法易于实现、运行速度快，是不错的近似算法。
第九章，动态规划
9.1，概念
动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。在学习动态规划之前需要明确掌握几个重要概念，如下：
- 阶段：对于一个完整的问题过程，适当的切分为若干个相互联系的子问题，每次在求解一个子问题，则对应一个阶段，整个问题的求解转化为按照阶段次序去求解。
- 状态：状态表示每个阶段开始时所处的客观条件，即在求解子问题时的已知条件。状态描述了研究的问题过程中的状况。
- 决策：决策表示当求解过程处于某一阶段的某一状态时，可以根据当前条件作出不同的选择，从而确定下一个阶段的状态，这种选择称为决策。
- 策略：由所有阶段的决策组成的决策序列称为全过程策略，简称策略。
- 最优策略：在所有的策略中，找到代价最小，性能最优的策略，此策略称为最优策略。
- 状态转移方程：状态转移方程是确定两个相邻阶段状态的演变过程，描述了状态之间是如何演变的。
9.2，背包问题
学习动态规划，这是一种解决棘手问题的方法，它将问题分成小问题，并先着手解决这些小问题，每个动态规划问题都是从一个网格入手，背包问题的网格如下：
工作原理：动态规划先解决子问题，再逐步解决大问题。从背包问题的网格计算入手，可明白为何计算小背包可装入的商品的最大价值。余下了空间时，你可根据这些子问题的答案来确定余下的空间可装入哪些商品。计算每个单元格的价值时，使用的公式都相同。 这个公式如下：
网格的行顺序发生变化时，最终答案没有变化。各行的排列顺序对最终结果无关紧要。
动态规划功能强大，它能够解决子问题并使用这些答案来解决大问题。 但仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。 这意味着使用动态规划算 法解决不了去巴黎玩的问题。
9.1，最长公共子串
通过动态规划问题，得到以下启示：
- 动态规划可帮助你在给定约束条件下找到最优解在背包问题中，你必须在背包容量给定的情况下，偷到价值最高的商品。
- 在问题可分解为彼此独立且离散的子问题时，就可使用动态规划来解决。
要设计出动态规划解决方案可能很难，这正是本节要介绍的。下面是一些通用的小贴士： - 每种动态规划解决方案都涉及网格。
- 单元格中的值通常就是你要优化的值。在前面的背包问题中，单元格的值为商品的价值。
- 每个单元格都是一个子问题，因此你应考虑如何将问题分成子问题，这有助于你找出网格的坐标轴。