一 、算法简介
1.1 二分查找
-
对于包含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.2 大O表示法
-
大O表示法是一种特殊的表示法，指出了算法的速度
-
大O表示法让你能够比较操作数，它指出了算法运行时间的增速。
-
大O 表示法指出了最糟情况下的运行时间
-
常见的大O运行时间：
-
O ( l o g n ) O(log n) O(logn)，对数时间，包括二分查找。
-
O ( n ) O(n) O(n)，线性时间，包括简单查找。
-
O ( n l o g n ) O(nlog n) O(nlogn)，包括快速排序——一种速度较快的排序算法。
-
O ( n 2 ) O(n^2) O(n2)，包括选择排序——一种速度较慢的排序算法。
-
O ( n ! ) O(n!) O(n!)，包括旅行商问题的解决方案——一种非常慢的算法。
大O运行时间 算法 O ( 1 ) O(1) O(1)（常量时间） 散列表 O ( l o g n ) O(log n) O(logn)（对数时间） 二分查找 O ( n ) O(n) O(n)（线性时间） 简单查找 O ( n l o g n ) O(nlog n) O(nlogn) 快速排序 O ( n 2 ) O(n^2) O(n2) 选择排序 O ( n ! ) O(n!) O(n!) 旅行商问题
-
-
启示：
- 算法的速度指的并非时间，而是操作数的增速。
- 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
- 算法的运行时间用大O表示法表示。
- O ( l o g n ) O(log n) O(logn)比 O ( n ) O(n) O(n)快，当需要搜索的元素越多时，前者比后者快得越多。
二、选择排序
2.1 数组与链表
-
数组
-
链表：链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起
-
数组与链表运行时间：
数组 链表 读取 O ( 1 ) O(1) O(1) O ( n ) O(n) O(n) 输入 O ( n ) O(n) O(n) O ( 1 ) O(1) O(1) 删除 O ( n ) O(n) O(n) O ( 1 ) O(1) O(1) -
索引：元素的位置称为索引
-
插入：使用链表时，插入元素很简单，只需修改它前面的那个元素指向的地址。而使用数组时，则必须将后面的元素都向后移。当需要在中间插入元素时，链表是更好的选择。
-
删除：当删除元素时，链表是更好的选择。
2.2 选择排序
-
遍历整个列表，找出最大的元素，并添加到一个新列表中。继续这样做，将得到一个有序列表
-
运行时间： O ( n 2 ) O(n^2) O(n2)
-
代码实现：
#找到最小值 def findSmallest(arr): smallest = arr[0] smallest_index = 0 for i in range(1, len(arr)): 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]))
三、递归
- 递归：调用自己的函数
- 递归条件：递归条件指的是函数调用自己
- 基线条件：基线条件指的是函数不再调用自己，从而避免形成无限循环。
- 栈
- 递归调用栈
- 栈的操作：压入和弹出
四、快速排序
4.1 分而治之（D&C）
-
一种著名的递归式问题解决方法。
-
步骤
- 找出基线条件
- 确定如何缩小问题的规模，使其符合基线条件
4.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表示法
- 快速排序的性能高度依赖于你选择的基准值
五、散列表
5.1 散列函数
-
将输入映射到数字
-
要求：
- 一致性
- 一一对应
-
散列函数总是将同样的输入映射到相同的索引
-
散列函数将不同的输入映射到不同的索引
-
散列函数知道数组有多大，只返回有效的索引
5.2 散列表
-
散列表：散列映射，映射，字典，关联数组
-
python提供的散列表为字典
-
散列表的应用：
- 模拟映射关系
- 防止重复
- 用作缓存
- 优点：用户更快地看到网页，服务器工作减少
-
冲突：给两个键分配的位置相同
- 反省：
- 散列函数很重要。尽量让散列函数将键均匀地映射到散列表的不同位置。
- 如果散列表存储的链表过长，散列表的速度将急剧下降
- 反省：
-
性能：散列表的查找、插入和删除速度都非常快
散列表（平均情况） 散列表（最糟情况） 数组 链 读取 O ( 1 ) O(1) O(1) O ( n ) O(n) O(n) O ( 1 ) O(1) O(1) O ( n ) O(n) O(n) 输入 O ( 1 ) O(1) O(1) O ( n ) O(n) O(n) O ( n ) O(n) O(n) O ( 1 ) O(1) O(1) 删除 O ( 1 ) O(1) O(1) O ( n ) O(n) O(n) O ( n ) O(n) O(n) O ( 1 ) O(1) O(1)
5.3 装填因子
- 装填因子=散列表包含的元素数 / 位置总数
- 装填因子=1：最佳情况，每个元素都有自己的位置
- 装填因子>1：元素数量超出了数组的位置数
- 当填装因子开始增大，你就需要在散列表中添加位置，这被称为调整长度
- 填装因子越低，发生冲突的可能性越小，散列表的性能越高。
- 经验规律：一旦填装因子大于0.7，就调整散列表的长度。
六、广度优先搜索
6.1 最短路径问题
- 步骤：
- 使用图来建立问题模型
- 使用广度优先搜索解决问题
6.2 广度优先搜索
-
用于图的查找算法
-
应用：
- 第一类问题：寻找路径：从节点A出发，有前往节点B的路径吗？
- 第二类问题：查找最短路径（段数最少的路径，而不是最快路径）：从节点A出发，前往节点B的哪条路径最短？
-
查找最短路径：
- 在广度优先搜索的执行过程中，搜索范围从起点开始逐渐向外延伸，即先检查一度关系，再检查二度关系
- 只有按添加顺序查找时，才能实现这样的目的
-
队列：
-
操作：入队和出队
-
操作顺序：先进先出
数据结构 操作顺序 栈 先进后出 队列 先进先出
-
-
实现图
- 有向图：其中的关系是单向的
- 无向图：没有箭头，直接相连的节点互为关系
-
算法工作原理：
- 创建一个队列，用于存储要检查的人
- 从队列中弹出一个人
- 检查这个人是否是目标
- 将这个人的所有邻居都列入队列
-
算法实现：
from collections import deque graph = {} graph["you"] = ["alice", "bob", "claire"] graph["bob"] = ["anuj", "peggy"] graph["alice"] = ["peggy"] graph["claire"] = ["thom", "jonny"] graph["anuj"] = [] graph["peggy"] = [] graph["thom"] = [] graph["jonny"] = [] def person_is_seller(name): return name[-1] == 'm' def search(name): search_queue = deque() search_queue += graph[name] searched = [] while search_queue: person = search_queue.popleft() if not person in searched: if person_is_seller(person): print(person + " is a mango seller!") return True else: search_queue += graph[person] searched.append(person) return False search("you") -
运行时间： O ( V + E ) O(V+E) O(V+E)，V为顶点数，E为边数
七、狄克斯特拉算法
7.1 使用狄克斯特拉算法
- 目的：找出最快路径
- 步骤：
- 找出“最便宜”的节点，即可在最短时间内到达的节点
- 更新该节点的邻居的开销，其含义将稍后介绍
- 重复这个过程，直到对图中的每个节点都这样做了
- 计算最终路径
7.2 术语
- 权重：狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重
- 加权图：带权重的图称为加权图。要计算加权图中的最短路径，可使用狄克斯特拉算法
- 非加权图：不带权重的图称为非加权图。要计算非加权图中的最短路径，可使用广度优先搜索
7.3 实现
graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["fin"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
graph["fin"] = {}
infinity = float("inf")
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)
八、贪婪算法
8.1 教室调度问题
- 思想：
- 选出结束最早的课，它就是要在这间教室上的第一堂课。
- 接下来，必须选择第一堂课结束后才开始的课。同样，你选择结束最早的课，这将是要在这间教室上的第二堂课。
8.2 背包问题
- 思想：
- 盗窃可装入背包的最贵商品。
- 再盗窃还可装入背包的最贵商品，以此类推。
8.3 集合覆盖问题
-
近似算法：在获得精确解需要的时间太长时，可使用近似算法
- 标准：速度有多快、得到的近似解与最优解的接近程度、
-
运行时间： O ( n 2 ) O(n^2) O(n2)
-
代码实现：
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() while states_needed: best_station = None states_covered = set() for station, states_for_station in stations.items(): covered = states_needed & states_for_station if len(covered) > len(states_covered): best_station = station states_covered = covered final_stations.add(best_station) states_needed -= states_covered print(final_stations) -
运行时间：
精确算法 贪婪算法 O ( n ! ) O(n!) O(n!) O ( n 2 ) O(n^2) O(n2)
8.4 旅行商问题
- 问题：要找出经由指定几个点的的最短路径——NP完全问题
九、K最近邻算法
9.1 创建推荐系统
-
特征抽取：毕达哥拉斯公式： ( a 1 − a 2 ) 2 + ( b 1 − b 2 ) 2 + ( c 1 − c 2 ) 2 + ( d 1 − d 2 ) 2 + ( e 1 − e 2 ) 2 \sqrt{(a_1-a_2)^2+(b_1-b_2)^2+(c_1-c_2)^2+(d_1-d_2)^2+(e_1-e_2)^2} (a1−a2)2+(b1−b2)2+(c1−c2)2+(d1−d2)2+(e1−e2)2
-
分类：编组
-
回归：预测结果
9.2 机器学习
-
OCR（光学字符识别）
- 训练：浏览大量的数字图像，将这些数字的特征提取出来。
- 遇到新图像时，你提取该图像的特征，再找出它最近的邻居都是谁！
-
朴素贝叶斯分类器
-
预测股票市场