算法图解_注释笔记

发表于 | 分类于

算法简介

二分查找

对数：对数运算是幂运算的逆运算。

公式 logn 相当于 log2n。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def binary_search(list, item):
    low = 0
    high = len(list)-1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]

        if guess == item:
            return mid

        if guess > item:
            high = mid-1
        else:
            low = mid+1

    return None

list = [1, 2, 5, 6, 7]
item = 7

print(binary_search(list, item))

大O表示法

假设列表包含n个元素。简单查找法需要检查每个元素，因此需要执行n次操作。使用大O表示法，这个运行时间为O(n)。
单位是秒吗？不是，大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较“操作次数”，它指出了算法运行时间的增速。随着n的增长，操作次数的变化趋势。

大O表示法指出了最糟情况下的运行时间

经常会遇到的5种大O运行时间：

  1. O(logn)，也叫对数时间，这样的算法包括二分查找
  2. O(n)，也叫线性时间，这样的算法包括简单查找
  3. O(n * logn)，这样的算法包括快速排序——一种速度较快的排序算法
  4. O(n2)，这样的算法包括选择排序——一种速度较慢的排序算法
  5. O(n!)，这样的算法包括旅行商问题的解决方案——一种非常慢的算法

不同算法运行时间：
不同算法运行时间

选择排序

数组和链表

数组添加新元素的速度很慢。就像你与朋友去看电影，找到地方就坐后又来了一位朋友，而当前坐的地方没有空位，你们就得转移，太麻烦了。
虽然可以预留座位，但是你额外请求的位置可能根本用不上，这将浪费内存。你没有使用，别人也用不了。人数超过预留座位后，你还得转移。

链表

链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起，根本就不需要移动元素。
链表相当于说“我们分开来坐”，因此，只要有足够的内存空间，就能为链表分配内存。

数组

需要同时读取所有元素时，链表的效率很高：你读取第一个元素，根据其中的地址再读取第二个元素，以此类推。但如果你需要跳跃（比如读取最后一个元素时），链表的效率真的很低。
就像排行榜网站上面，想查看下一项内容，就要点击“下一页”才能看到。

数组和链表：
数组和链表

在中间插入

使用链表时，插入元素很简单，只需修改它前面的那个元素指向的地址。
而使用数组时，则必须将后面的元素都向后移。如果没有足够的空间，可能还得将整个数组复制到其他地方。
因此，当需要在中间插入元素时，链表是更好的选择。

删除

要删除元素时，链表也是更好的选择，因为只需修改前一个元素指向的地址即可（前提是能直接访问到这个元素）。而使用数组时，删除元素后，必须将后面的元素都向前移。

选择排序

假设你的计算机存储了很多乐曲。对于每个乐队，你都记录了其作品被播放的次数。你要将这个列表按播放次数从多到少的顺序排列，从而将你喜欢的乐队排序。

选择排序：遍历列表，找到列表中播放次数最大的歌曲，然后将该歌曲添加到一个新列表中。重复这个过程。
*大O表示法省略诸如1/2这样的常数，因此O(n × 1/2 × n)简单地写作O(n × n)或O(n2)。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def findSmallest(arr):
    smallest_index = 0
    smallest = arr[0]
    for i in range(1, len(arr)):
        if smallest > arr[i]:
            smallest = arr[i]
            smallest_index = i
    return smallest_index


def selectionSort(arr):
    newArr = []
    for _ in range(len(arr)):  # 执行n遍
        smallest = findSmallest(arr)
        newArr.append(arr.pop(smallest))
    return newArr

print(selectionSort([2, 76, 1, 6, 12, 75, 2, 21]))

递归

如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。

基线条件和递归条件

递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。

栈

栈就好比一个待办事项清单–一叠便条，这个待办事项清单只有两种操作：压入（插入）和弹出（删除并读取）。

快速排序

分而治之

分而治之（divide and conquer，D&C） ——一种著名的递归式问题解决方法。

D&C的工作原理：

  1. 找出简单的基线条件
  2. 确定如何缩小问题的规模，使其符合基线条件

D&C并非可用于解决问题的算法，而是一种解决问题的思路。

编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时，请检查基线条件是不是这样的。

分治：
分治1
分治2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
arr = [2, 1, 5, 2, 1, 3, 6]

# 尾调用优化
def calculSum(sum, arr):
    if len(arr) == 1:
        return sum + arr[0]
    else:
        return calculSum(sum+arr[0], arr[1:])

print(calculSum(0, arr))

# 一般形式
def calculSum(arr):
    if len(arr) == 1:
        return arr[0]
    else:
        return arr[0] + calculSum(arr[1:])

print(calculSum(arr))

快速排序

  1. 选择基准值
  2. 分区（partitioning）：根据基准值把所有元素分为比基准值小的元素和比基准值大的元素
  3. 对这两个子数组进行快速排序
  4. 合并

以此类推

归纳证明：归纳证明是一种证明算法行之有效的方式，它分两步：基线条件和归纳条件。

对于快速排序，基线条件是，我证明这种算法对空数组或包含一个元素的数组管用。归纳条件是，我证明如果快速排序对包含一个元素的数组管用，对包含两个元素的数组也将管用；如果它对包含两个元素的数组管用，对包含三个元素的数组也将管用，以此类推。
因此，我可以说，快速排序对任何长度的数组都管用。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
def qsort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]

    less = [i for i in arr[1:] if i <= pivot]
    greater = [i for i in arr[1:] if i > pivot]
    
    return qsort(less) + [pivot] + qsort(greater)

print(qsort([7, 32, 1, 3, 87, 23, 64, 11, 40]))

再谈大O表示法

常见算法复杂度：
常见算法复杂度

比较归并排序和快速排序

快速排序平均情况下运行时间为O(n logn)，最糟的情况下为O(n2)，而归并排序的运行时间总是O(n logn)。

1
2
3
4
5
6
from time import sleep

def print_items2(list):
    for item in list:
        sleep(1)
        print(item)

上面函数的运行时间也为O(n)，但是因为休眠所以慢得多。在O(n)中，n实际上指的是次数，而运行总时间为c * n，c为算法所需的固定时间量，被称为常量。所以上面算法的总时间为1秒 * n。
如果两种算法的大O运行时间不同，这种常量将无关紧要。但有时候，常量的影响可能很大，对快速查找和合并查找来说就是如此。快速查找的常量比归并查找小，因此如果它们的运行时间都为O(n * logn)，快速查找的速度将更快。
平均情况下，快排比归并的速度更快。而相对于最糟的情况，平均情况的可能性要大得多。

平均情况和最糟情况

最糟情况：假设你总是将第一个元素用作基准值，且要处理的数组是有序的。
快排最糟

平均情况：
快排平均

总结：

D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组。

  • 实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n * logn)
  • 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在
  • 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时， O(logn)的速度比O(n)快得多

散列表

Hash Table

散列函数

散列函数
散列函数

散列函数准确地指出了元素的存储位置，你根本不用查找！之所以能够这样，具体原因如下:

  • 散列函数总是将同样的输入映射到相同的索引
  • 散列函数将不同的输入映射到不同的索引
  • 散列函数知道数组有多大，只返回有效的索引

散列表是一种包含额外逻辑的数据结构。数组和链表都被直接映射到内存，但散列表更复杂，它使用散列函数来确定元素的存储位置，使用数组来存储数据，因此其获取元素的速度与数组一样快。

冲突

冲突（collision），处理冲突的方式很多，最简单的办法如下：如果两个键映射到了同一个位置，就在这个位置存储一个链表。

散列函数很重要。最理想的情况是，散列函数将键均匀地映射到散列表的不同位置。

如果散列表存储的链表很长，散列表的速度将急剧下降。

性能

要避免冲突，需要有：

  • 较低的填装因子
  • 良好的散列函数

填装因子，即占用的位置数/位置总数。一旦填装因子大于0.7，就需要调整散列表的长度。调整长度的开销很大，因此你不会希望频繁地这样做。
良好的散列函数，让数组中的值呈均匀分布，糟糕的散列函数让值扎堆，导致大量的冲突。

广度优先搜索

图，图由节点和边组成，一个节点可能与众多节点直接相连，这些节点被称为邻居。
广度优先搜索（BFS），让你能够找出两样东西之间的“最短”距离，是一种用于图的查找算法。回答两类问题：

  1. 从节点A出发，有前往节点B的路径吗？
  2. 从节点A出发，前往节点B的哪条路径最短？

队列，FIFO的数据结构，类似于排队上车。
栈，LIFO的数据结构。类似于桌子上的一叠纸牌。
树，是一种特殊的单向图。

实现图

表示邻近关系可以用散列表。

1
2
3
4
graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
...

这被称为有向图（directed graph），其中的关系是单向的。因此，Anuj是Bob的邻居，但Bob不是Anuj的邻居。无向图（undirected graph）没有箭头，直接相连的节点互为邻居。

实现算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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"] = ['you']

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!")
                break
            else:
                search_queue += [p for p in graph[person] if p not in searched]
                searched.append(person)

def person_is_seller(name):
    return name[-1] == 'm'  # 假设条件

search('you')
print('end')

你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列。
对于检查过的人，务必不要再去检查，否则可能导致无限循环。

运行时间

如果你在你的整个人际关系网中搜索，就意味着你将沿每条边前行，因此运行时间至少为O(边数)。
你还使用了一个队列，其中包含要检查的每个人。将一个人添加到队列需要的时间是固定的，即为O(1)，因此对每个人都这样做需要的总时间为O(人数)。
所以，广度优先搜索的运行时间为O(人数 + 边数)，这通常写作O(V + E)，其中V为顶点（vertice）数，E为边数。

狄克斯特拉算法

狄克斯特拉算法

Dijkstra’s algorithm

4个步骤：

  1. 找出当前节点（可能是起点或其他节点）的邻居节点中，最便宜的（未处理）节点。对于还不知道的节点，暂假设为无穷大
  2. 计算经最便宜的节点前往其各个邻居所需的开销。更新从起点到各个节点的最短开销
  3. 重复这个过程，直到对图中每个节点都这样做了
  4. 计算最终路径

术语

带权重的图称为加权图（weighted graph），不带权重的图称为非加权图（unweighted graph）。
狄克斯特拉算法，让你能够找出加权图中前往X的最短路径。狄克斯特拉算法只适用于有向无环图，在无向图中，每条边都是一个环。

案例：换钢琴

交换图：
交换图

交换第二步：
交换第二步

最终路径：
最终路径

负边权

负边权路径：
负边权路径

如果有负权边，就不能使用狄克斯特拉算法。因为负权边会导致这种算法不管用。这是因为狄克斯特拉算法这样假设：对于处理过的节点，没有前往该节点的更短路径。这种假设仅在没有负权边时才成立。
在包含负权边的图中，要找出最短路径，可以用贝尔曼福德算法（Bellman-Fordalgorithm）。

实现

要编写解决这个问题的代码，需要三个散列表：
三个散列表

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import operator

# 路线图表
graph = {}
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')
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):
    unpro_costs = {k: v for k, v in costs.items() if k not in processed}
    return min(unpro_costs, key=lambda x: unpro_costs[x]) if unpro_costs else None


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)

贪婪算法

贪婪算法，每步都采用局部最优解，最终得到的就是近似全局最优解。
完美是优秀的敌人，有时候只需找到一个能够大致解决问题的算法，此时贪婪算法正好派上用场。因为它们实现起来很容易，得到的结果又与正确结果相当接近。

集合覆盖问题

集合覆盖问题

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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 and stations:
    best_station = None
    states_covered = set()
    for station, states_for_station in stations.items():
        coverd = states_needed & states_for_station  # % 交集，| 并集，- 差集
        if len(coverd) > len(states_covered):
            best_station = station
            states_covered = coverd

    final_stations.add(best_station)
    states_needed -= states_covered
    stations.pop(best_station)

print(final_stations)
print(states_needed)

NP 完全问题

旅行商问题和集合覆盖问题有一些共同之处：你需要计算所有的解，并从中选出最小/最短的那个。这两个问题都属于NP完全问题。

NP完全问题无处不在！没办法判断问题是不是NP完全问题，但还是有一些蛛丝马迹可循的：

  • 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢
  • 涉及“所有组合”的问题通常是NP完全问题
  • 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题
  • 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题
  • 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题
  • 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题

动态规划

背包问题

  1. 网格：

动态规划-网格

  1. 多行：
    动态规划-多行

  2. 更新：
    动态规划-更新

  3. 最终:
    动态规划-最终

背包问题FAQ

问：沿着一列往下走时，最大价值有可能降低吗？
答：不可能。每次迭代时，你都存储当前的最大价值。最大价值不可能比以前低！

问：行的排列顺序发生变化时结果会变化吗？
答：最终结果不会变化。

问：增加一件更小（重量有小数点）的商品将如何呢
答：你需要考虑的粒度更细，因此必须调整网格。

最长公共子串

动态规划可帮助你在给定约束条件下找到最优解。在背包问题中，你必须在背包容量给定的情况下，偷到价值最高的商品。
在问题可分解为彼此独立且离散的子问题时，就可使用动态规划来解决。

最长公共子串：
最长公共子串

这个问题的最终答案并不在最后一个单元格中。

最长公共子序列

FOSH和FORT，最长公共子串是2。FOSH和FISH，最长公共子串也是2。但是后者的相同字母（也就是最长公共子序列）更多，更相像。

最长子序列：
最长子序列

动态规划的实际应用：

  • 生物学家根据最长公共序列来确定DNA链的相似性，进而判断度两种动物或疾病有多相似。还被用来寻找多发性硬化症治疗方案
  • git diff
  • Microsoft Word的断字功能

动态规划的特点：

  • 需要在给定约束条件下优化某种指标时，动态规划很有用
  • 问题可分解为离散子问题时，可使用动态规划来解决
  • 每种动态规划解决方案都涉及网格
  • 单元格中的值通常就是你要优化的值
  • 每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题
  • 没有放之四海皆准的计算动态规划解决方案的公式

K最近邻算法

k-nearest neighbours，KNN。

K最近邻

你将使用KNN来做两项基本工作——分类和回归：分类就是编组；回归就是预测结果（如一个数字）。

特征抽取，即将物品（如水果或用户）转换为一系列可比较的数字。能否挑选合适的特征事关KNN算法的成败。

其他数据结构

树

对于树中的每个节点，左子节点的值都比它小，而右子节点的值都比它大。
在二叉查找树中查找节点时，平均运行时间为O(logn)，但在最糟的情况（不平衡的树）下所需时间为O(n)，但是插入和删除所需时间都为O(logn)。
有序数组进行二分查找，查找所需时间O(logn)，插入和删除都为O(n)。

二叉树的确定：不能随机访问。

反向索引

反向索引（inverted index），讲单词映射到包含它的页面（文档）。常用来创建搜索引擎。

傅里叶变换

傅里叶变换，“给它一杯冰沙，它能告诉你其中包含哪些成分”。常用来处理MP3音乐格式，地震预测和DNA分析。

MapReduce

MapReduce，一种流行的分布式算法，可让算法在多台计算机上运行。可通过Hadoop来使用它。

应用场景：
对包含数十亿乃至数万亿行的数据库表进行复杂的SQL查询。
处理100万个小任务，每个任务需要10秒。

MapReduce基于两个简单的理念：映射（map）函数，归并（reduce）函数

映射函数

1
2
arr1 = [1, 2, 3, 4, 5]
arr2 = map(lambda x: x*2, arr1)

归并函数

1
2
3
4
from functools import reduce

arr1 = [1, 2, 3, 4, 5]
total = reduce(lambda x, y: x+y, arr1)

布隆过滤器

用散列表进行数据搜索是很快的，时间复杂度为O(1)，但是如果数据量特别大时（比如Google管理的数万亿个网页的索引），这个散列表将占用大量的存储空间。
布隆过滤器是一种概率型数据结构，非常适合用于不要求答案绝对准确的情况，比如对安全网址提示工具来说，这样说完全可行：“我们认为这个网站可能是恶意的，请倍加小心。”。

SHA算法

安全散列算法（secure hash algorithm）。用于创建散列表的散列函数根据字符串生成数组索引，而SHA根据字符串生成另一个字符串。
SHA被广泛用于计算密码的散列值。这种散列算法是单向的。

局部敏感的散列算法

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

应用场景：
Google使用Simhash来判断网页是否已收集。
老师使用Simhash来判断论文是否是从网上抄的。

RSA

公钥加密，私钥解密。私钥加密，公钥解密。

线性规划

线性规划用于在给定约束条件下最大限度地改善指定的指标。
例如，假设你所在的公司生产两种产品：衬衫和手提袋。衬衫每件利润2美元，需要消耗1米布料和5粒扣子；手提袋每个利润3美元，需要消耗2米布料和2粒扣子。你有11米布料和20粒扣子，为最大限度地提高利润，该生产多少件衬衫、多少个手提袋呢？在这个例子中，目标是利润最大化，而约束条件是拥有的原材料数量。

欢迎打赏