本文最后更新于：2022年7月8日下午5点08分

Grokking Algorithms, by Aditya Bhargava。本书代码地址。

1 算法简介

二分法

对于包含n个元素的列表，简单查找法最多需要n步（线性时间），而二分法查找最多需要\(log_2\ n\)步（简写为\(log\ n\)）（对数时间 / l\(og\)时间）。

仅当列表是有序的时候，二分查找才管用。

大O表示法（Big O notation）——运行时间

简单查找法编写起来容易，出bug可能性小，但运行时间慢。二分法相反。大O表示法给出的运行时间是最大运行时间。

常见大O运行时间

\(O(log\ n)\)，对数时间，包括二分查找
\(O(n)\)，线性时间，包括简单查找
\(O(n\ log\ n)\)，包括快速排序——一种速度较快的排序算法，以及合并排序
\(O(n^2)\)，包括选择排序——一种速度较慢的排序算法
\(O(n!)\)，包括后续的旅行商问题的解决方案——一种非常慢的算法

# 二分法 #################################

def binary_search(numList,item):
    low = 0
    high = len(numList) - 1
    while low <= high:
        mid = (low + high) // 2
        guess = numList[mid]
        if guess < item:
            low = mid + 1
        elif guess > item:
            high = mid -1
        else:
            return guess
    return None

numList = list(range(0,100))
guess = binary_search(numList,34)
print(guess)

# exercise #################################
'''
# 1.1,1.2
import math

print(math.log(128,2)) # 7步
print(math.log(128*2,2)) # 8步
'''
'''
1.3 O(log n)
1.4 O(n)
1.5 O(n)
1.6 O(n)
'''
# 阶乘 ##################
'''
import math
print(math.factorial(5)) # 120
'''

2 选择排序

数组和链表

数组元素在内存中都是相连的（紧靠在一起）。

分配的内存空间如果小于元素个数，就需要转移位置。为了避免这一点，可以申请预留位置，但这样造成了内存的浪费。元素个数大于申请预留位置的个数后还要转移位置。但数组可以直接访问任何元素。在同一数组中，所有元素的类型都必须相同（都为int、double等）。

数组的优势在读取元素方面，数组支持随机访问。
链表中的元素可以存储在内存中的任何地方。

链表中的每个元素都存储了下一个元素的地址，从而使一系列随机的内存串在一起。但是正因为这个特点，链表不能跳跃访问中间的元素，而必须从第一个元素开始向后一级一级访问。

链表的优势在插入和删除元素方面，链表只支持顺序访问。

	数组	链表
读取	O(1)	O(n)
插入	O(n)	O(1)
删除	O(n)	O(1)

选择排序

遍历列表（n个元素），依次找出最大值、次大值......最小值，存储到新列表中。每个值遍历一遍，要遍历n遍，每一遍里面要查找n、n-1......1次。平均每次查找0.5xn次，因此运行时间为O(nx0.5xn)，但大O表示法省略0.5这样的常数，因此简单的写作O(n²)。

# 找到最小值的索引 ########################
def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1,len(arr)): # 不包含0位置处的值（len()也不包含最后一个值，数值是0到len()-1）
        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))
        # 最开始总数是n，第一次遍历，将arr中选出来的最小值删除，总数为n-1，第二次遍历再删掉，总数为n-2，依次递归
        # [pop()函数删除列表中的值并！！返回被删除的值！！]
        # arr.pop()将arr中的值删除并返回这个值，这里也就是最小值，然后这个值被append函数添加到newArr中
        # 也就是说第一次遍历添加的是n个数中的最小值，第二次添加的是n-1个数中的最小值
    return newArr
    
arr = [5,2,1]
newArr = selectionSort(arr)
print(newArr)

# excerice #############################
'''
问题:如果从第一个元素处插入元素，则后面的元素都要后移一位，这样运行时间就是O(n)
2.1 链表
2.2 链表
2.3 有序数组
2.4 慢，如果用二分法查找用户名，数组必须是有序的，加入一个A开头的名字注册用户，这个用户名将插入到数组末尾。因此必须对数组排序
2.5 查找时速度比数组慢，但比链表快；而插入时速度比数组快，但预链表相当。
    Facobook使用的是基于众多不同的数据结构（散列表，B树等）的数据库。
'''

3 递归

从套娃盒子中拿出钥匙的两种方法

while循环（自己创建盒子堆）

创建一个要查找的盒子堆
从盒子堆取出一个盒子，在里面找。
如果找到的是盒子，就将其加入盒子堆中，以便以后再查找。
如果找到钥匙，则大功告成！
如果没找到钥匙，回到第二步。

def look_for_key(main_box):
    pile = main_box.make_a_pile_to_look_through()
    while pile is not empty:
        box = pile.grab_a_box()
        for item in box:
            if item.is_a_box():
            	pile.append(item)
            elif item.is_a_key():
            	print "found the key!"

递归——函数调用自己（盒子堆存储在栈中）

检查盒子中的每样东西
如果是盒子，就回到第一步
如果是钥匙，就大功告成！

def look_for_key(box):
    for item in box:
        if item.is_a_box():
        	look_for_key(item) # 递归
        elif item.is_a_key():
        	print "found the key!"

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

基线条件和递归条件

def countdown(i):
    print(i)
    if i <=0: # 基线条件，何时停止，函数不再调用自己
        return
    else: # 递归条件，函数调用自己
        countdown(i-1)

countdown(3) # 调用函数

栈、调用栈（call stack）

栈只有两种操作：压入（插入）和弹出（删除并读取）

def greet(name):
    print('hello,',name+'!')
    greet2(name)
    print('greeting ready to say bye...')
    bye()
def greet2(name):
    print('how are you,',name+'?')
def bye():
    print('ok bye!')

greet('zhao')

递归调用栈

def fact(x):
    if x <= 1:
        return 1
    else:
        return x * fact(x-1)

print(fact(3))

回到最开始的套娃盒子问题，while循环需要自己创建盒子堆，而递归不需要，因为盒子堆存储在栈中。这样使得使用栈很方便，但是这样可能会占用大量内存，如果栈很高，计算机就存储了大量函数调用的信息，这样可以重新编写代码转而使用循环，或者使用尾递归。

'''
3.1 首先调用了greet函数，函数未执行完成，又调用了greet2函数
3.2 栈溢出。栈将不断地增大。每个程序可使用的调用栈空间都有限，
    程序用完这些空间（终将如此）后，将因栈溢出而终止。
'''

4 快速排序

分而治之（divide and conquer, D&C）

使用D&C解决问题的两个步骤

找出基线条件，这种条件必须尽可能简单
不断将问题分解（或者说所小规模），直到符合基线条件

练习

# 4.1 循环
def sum(arr):
    total = 0
    for i in arr:
        total += i
    return total

print(sum([5,2,3]))

# 4.1 递归
def sum(arr):
    if arr == []: return 0
    return arr[0] + sum(arr[1:])

print(sum([1,2,4,5]))

# 4.2
def num_of_items(arr):
    if arr == []: return 0
    return 1 + num_of_items(arr[1:])

print(num_of_items([1,2,3,4,5]))

# 4.3
def max(list):
    if len(list) == 2:
        return list[0] if list[0] > list[1] else list[1]
    sub_max = max(list[1:])
    return list[0] if list[0] > sub_max else sub_max

print(max([1,2,3,4,5]))

1 2	`# 基线条件是数组中只剩一个元素。 # 递归条件是将数组分成两半，将其中一半丢弃，再对另一半执行二分查找`

快速排序

快速排序的工作原理

首先，从数组中选择一个元素作为基准值（pivot）
然后，找出比基准值小的元素以及比基准值大的元素，这一步叫分区，数组被分成三分
- 一个所有小于基准值的数构成的子数组
- 基准值
- 一个所有大于基准值的数构成的子数组
递归

# 快速排序算法
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([1,3,9,0]))

再谈大O表示法

快速排序和合并排序比较

快速排序的平均运行时间为\(O(n\ log\ n)\)，最糟糕情况为\(O(n^2)\)
快速排序的常量比合并排序的常量小
快速排序遇到平均情况的可能性比最糟糕情况大的多
因此，快速查找一般更快

'''
4.5 O(n)
4.6 O(n)
4.7 O(1)
4.8 O(n^2)
'''

5 散列表（Hash Tables）

散列函数（Hash哈希函数）

散列函数是将输入映射到数字的函数。散列表也使用数组来存储数据。Python提供的散列表实现为字典。散列表是无序的。

'''
5.1 是
5.2 否
5.3 否
5.4 是
'''

应用案例

用于查找

模拟映射关系，将键映射到值。

phone_book = {}
phone_book["Jenny"] = 238725
phone_book["Emergency"] = 911
print(phone_book["Emergency"])

防止重复

def check_voter(name):
    voted = {}
    voted["abc"] = 123
    if voted.get(name): # dict.get(key,default=None)
        print("Kick them out!")
    else:
        print("Let the vote")

check_voter("abc")

用作缓存

缓存的数据存储在散列表中。网站一般将页面url映射到页面数据

cache = {}
cache["https://babblingme.gitee.io"] = 123

def get_page(url):
    if cache.get(url):
        return cache[url]
    else:
        data = get_data_from_server(url)
        cache[url] = data
        return data

def get_data_from_server(url):
    return "This is data"

print(get_page("https://babblingme.gitee.io"))

冲突与性能

在同一位置处存储不同的键值对就会产生冲突，需要在该位置处添加指向另一位置处的链表解决冲突。如果链表很长就会影响性能。

	散列表（平均）	散列表（最坏）	数组	链表
查找	O(1)	O(n)	O(1)	O(n)
插入	O(1)	O(n)	O(n)	O(1)
删除	O(1)	O(n)	O(n)	O(1)

要避免冲突，需要有较低的装填因子和良好的散列函数。

装填因子=数列表包含的元素数/位置总数。装填因子度量的是散列表中有多少位置是空的。一旦装填因子增大（一般大于0.7就需要调整，大于1意味着有些位置会有两个键值，就需要创建链表），就需要在散列表中添加位置，即调整长度。

良好的散列函数让数组中的值呈均匀分布。糟糕的散列函数让值扎堆，导致大量冲突。

'''
# 感觉答案不太对头
5.5 D
5.6 B
5.7 CD
'''

6 广度优先搜索（Breadth-First Search）

图简介

解决最短路径问题（shorterst-path problem）的算法被称为广度优先搜索。需要两个步骤

使用图来建立问题模型
使用广度优先搜索解决问题

图模拟一组连接。图由节点（node）和边（edge）组成，一个节点可能与众多节点直接相连，这些节点被称为邻居。

广度优先搜索

广度优先搜索是一种用于图的查找算法，可以帮助回答两类问题

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

广度优先搜索先检查一度关系，再检查二度关系。

实现按添加顺序检查的数据结构就是队列（queue）。队列类似于栈，不能随机地访问队列中的元素。队列只支持两种操作：入队和出队。队列是一种先进先出（First In First Out，FIFO）的数据结构，而栈是一种后进先出（Last In First Out，LIFO）的数据结构。可以比较形象的理解为，队列是前后堆叠，而栈是上下堆叠。

实现图

Anuj、Peggy、Thom和Jonny都没有邻居，这是因为虽然有指向它们的箭头但是没有从它们出发指向别人的箭头，这种叫有向图（directed graph），其关系是单向的。因此Anuj是Bob的邻居，但Bob不是Anuj的邻居。无向图（undirected graph）没有箭头，直接相连的节点互为邻居。

graph = {}
graph["You"] = ["alice","bob","claire"] # you被映射到一个包含其所有邻居的数组
graph["bob"] = ["anuj","peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["jonny","thom"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []
# 散列表是无序的，因此添加键值对的顺序无关紧要
# 但是后面的搜索列表必须要按先后顺序进行搜索，所以采用队列

实现算法

from collections import deque

def person_is_seller(name):
    return name[-1] == "m" # 最后一个字母是m返回真

def search(name):
    search_queue = deque() # 创建双端队列，搜索列表必须是队列，以保证按加入顺序搜索列表中的人
    search_queue += graph[name]
    searched = []
    while search_queue:
        person = search_queue.popleft() # pop用于stack，popleft用于collections
        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 print("No mango seller")

search("claire")

运行时间

广度优先搜索的运行时间是O(人数+边数)，O(V+E)，V是顶点数vertice，E是边数edge。

'''
6.3 B可行
6.4 # 拓扑排序，A任务依赖于B，在列表中A就必须在B后边
1) 起床
2) 锻炼
3) 刷牙
4) 打包午餐
5) 洗澡
6) 吃早餐
7) 穿衣服
6.5 AC # 树是图的子集
'''

7 迪克斯特拉算法

简介

带权重的图称为加权图（weighted graph），不带权重的图称为非加权图（unweighted graph）。广度优先搜索可计算非加权图中的最短路径。迪克斯特拉算法（Dijkstra's algorithm）可计算加权图中的最短（也就是最快，或总权重最小）路径。

从一个节点出发，走一圈后又回到这个节点，这就是一个环。环增加了权重，绕环的路径不可能是最短路径。无向图是两个节点彼此指向对方，其实就是环。在无向图中，每条边都是一个环。迪克斯特拉算法只适用于有向无环图（directed acyclic graph, DAG）。

迪克斯特拉算法的四个步骤：

找出最便宜的节点，即可在最短时间内前往的节点。
对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。
重复这个过程，直到对图中的每个节点都这样做了（除终点）。
计算最终路径。

换钢琴

Rama，想拿一本乐谱换架钢琴。

Alex说：“这是我最喜欢的乐队Destroyer的海报，我愿意拿它换你的乐谱。如果你再加5美元，还可拿乐谱换我这张稀有的Rick Astley黑胶唱片。”

Amy说：“哇，我听说这张黑胶唱片里有首非常好听的歌曲，我愿意拿我的吉他或架子鼓换这张海报或黑胶唱片。”

Beethoven惊呼：“我一直想要吉他，我愿意拿我的钢琴换Amy的吉他或架子鼓。“

父节点	节点	开销
乐谱	黑胶唱片	5
乐谱	海报	0
-	低音吉他	\(\infty\)
-	架子鼓	\(\infty\)
-	钢琴	\(\infty\)

注：无穷大代表暂时不知道如何从起点前往这些节点。

第一步：找出最便宜的节点。换海报最便宜
第二步：计算前往该节点的各个邻居的开销。

父节点	节点	开销
乐谱	黑胶唱片	5
乐谱	海报	0
海报	*低音吉他*	30
海报	架子鼓	35
-	钢琴	\(\infty\)

再执行第一步：下一个最便宜的节点是黑胶唱片——需要额外支付5美元。
再执行第二部：更新黑胶唱片的各个邻居的开销。

父节点	节点	开销
乐谱	黑胶唱片	5
乐谱	海报	0
*黑胶唱片*	*低音吉他*	20
黑胶唱片	架子鼓	25
-	钢琴	\(\infty\)

注：开销价格为途径的总价格。经“黑胶唱片”前往“低音吉他”和“架子鼓”的开销比经“海报”前往这两个节点要低。所以将这两个节点的父节点改为“黑胶唱片”

最便宜的是低音吉他，先更新其开销

父节点	节点	开销
乐谱	黑胶唱片	5
乐谱	海报	0
黑胶唱片	低音吉他	20
黑胶唱片	架子鼓	25
*低音吉他*	钢琴	40

然后未处理节点中最便宜的是架子鼓，更新其开销

父节点	节点	开销
乐谱	黑胶唱片	5
乐谱	海报	0
黑胶唱片	低音吉他	20
黑胶唱片	架子鼓	25
*架子鼓*	钢琴	35

这里经架子鼓到达钢琴开销更低，因此更新钢琴父节点为架子鼓。最终路径就可以确定下来了

钢琴的父节点是架子鼓，架子鼓的父节点是黑胶唱片，黑胶唱片的父节点是乐谱。

负权边

迪克斯特拉算法假设：对于处理过的海报节点，没有前往该节点的更短路径。这种假设仅在没有负权边时才成立。因此，不能将迪克斯特拉算法用于包含负权边的图。包含负权边的图，可以用贝尔曼-福德算法（Bellman-Ford algorithm）。

算法实现

# 散列表-图
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):
    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(parents)

练习题，顺便简化了散列表的创建

'''
7.1 A 8, B 60, C 4 但无法用迪克斯特拉算法求解
'''
# 7.1 A
#######################直接创建字典
# 散列表-图
graph = {"start":{"a":5,"b":2},"a":{"c":2,"d":4},
        "b":{"a":8,"c":7},"c":{"fin":1},
        "d":{"c":6,"fin":3},"fin":{}}

# 散列表-开销
infinity = float("inf")
costs = {"a":5,"b":2,"c":infinity,"d":infinity,"fin":infinity}

# 散列表-父节点
parents = {"a":"start","b":"start","c":None,"d":None,"fin":None}

# 数组-处理过的节点
processed = []
##############################调用迪克斯特拉算法
print(parents)
# 输出结果： {'a': 'start', 'b': 'start', 'c': 'a', 'd': 'a', 'fin': 'c'}
# 通过父节点推断除最短路径，fin->c->a->start，然后权重相加得到8

8 贪婪算法（贪心算法）

教室调度和背包问题

贪婪算法：每步都选择局部最优解，得到的就是全局最优解。

有如下课表，将尽可能多的课程安排在一间教室

选出结束最早的课，也就是这间教室上的第一节课。
然后选择第一节课结束之后才开始的课。重复以上步骤就可以了。

小偷背着可装入一定重量的背包，在商场盗窃各种商品装入背包，如何利益最大化

盗窃可装入背包的最贵商品
再盗窃还可装入背包的最贵商品，以此类推。

这样贪婪算法找到的并不是最优解，只是接近最优解。

'''
8.1 1)找到最大程度贴合卡车尺寸的箱子，2)在装入能装入卡车的最大尺寸的箱子。不能
8.2 1)找出最大价值的旅行，2)找出剩余天数内能进行的最大价值旅行。不能
'''

集合覆盖问题（set covering problem）

列出每个可能的广播台集合，这被称为幂集（power set），可能的子集有2²个（详见）。
在这些集合中，选出覆盖全美50个州的最小集合。

因为有2ⁿ个可能的集合，所以运行时间为\(O(2^n)\)。运行时间太长了。可以通过贪婪算法近似求解。

近似算法

选出一个覆盖最多未覆盖州的广播台。
重复第一步，直到覆盖了所有州。

这是一种近似算法（approximation algorithm），在获得精确解需要的时间太长时，可使用近似算法。判断近似算法优劣的标准如下：

速度有多快。
得到的近似解与最优解的接近程度。

在上个例子中，贪婪算法的运行时间为\(O(n^2)\)，其中\(n\)为广播台数量。下面看看解决在这个问题的代码，这里做了简化。

# 近似算法
states_needed = set(["mt","wa","or","id","nv","ut","ca","az"]) # 需要覆盖的州。这是集合，类似于列表，但集合不能包含重复的元素
stations = {}
stations["knoe"] = 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"])
finall_stations = set()

while states_needed:
    best_station = None # 可覆盖最多未覆盖州的广播台
    states_covered = set() # 包含该广播台覆盖的所有未覆盖州
    for station, states in stations.items(): # 取出stations的两个元素（键值），第一个是广播台，第二个是该广播台覆盖的州
        covered = states_needed & states
        if len(covered) > len(states_covered): # 只有没完全覆盖就进入循环
            best_station = station
            states_covered = covered
    states_needed -= states_covered # 减掉以覆盖州
    finall_stations.add(best_station) # 选出来的最适合的广播台（每次运行结果不一样）

print(finall_stations)

交集、差集和并集

fruits = set(["avocado","tomato","banana"])
vegetables = set(["beets","carrots","tomato"])
test = fruits - vegetables # 交集&，并集|，差集-（差集是剔除前者集合中后者集合含有的元素）
print(test)

练习题

'''
8.3 不是
8.4 是，贪心算法是先找到局部最优解，而广度优先搜索及迪克斯特拉算法每一步都是找到最短路径（局部最优解），因此属于贪心算法。
8.5 是
'''

NP完全问题

旅行商问题和集合覆盖问题有一些共同指出：需要计算所有解，并从中挑出最小/最短的那个。这两个问题都属于NP完全问题。NP完全问题的意思是多项式复杂程度的非确定性问题（Non-deterministic Polynomial Complete），其简单定义就是以难解著称的问题。NP完全问题基本不可能快速求解，只能近似求解。贪婪算法是不错的近似算法。

如何识别NP完全问题

无法直接判断问题是不是NP完全问题，只有一些细节值得注意

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

练习题

'''
8.6 是，经由几个点的最短路径问题，就是旅行商问题
8.7 是，集合覆盖问题？
8.8 是，集合覆盖问题
'''

9 动态规划

背包问题

小偷背着一个可装4磅东西的背包，可盗窃的商品有：

商品	价格	重量
音响	3000美元	4磅
笔记本电脑	2000美元	3磅
吉他	1500美元	1磅

如何让盗取的商品价值最高？

简单算法

排列组合有2ⁿ种情况，运行时间太慢，贪心算法可以得到近似解，但不一定是最优解。

动态规划

动态规划先解决子问题，再逐步解决大问题。每个动态规划算法都从一个网格开始，背包问题的网格如下。

	1	2	3	4
吉他	1500G	1500G	1500G	1500G
音响	1500G	1500G	1500G	3000S
笔记本电脑	1500G	1500G	2000L	*3500L G*

1
2

cell[i][j] = cell[i-1][j] or value + cell[i-1][j-weight] # value是当前商品的价值，weight是当前商品重量
# 当前单元格的值=上一个单元格的值 或者 当前商品的价值+剩余空间的价值

背包问题FAQ

4件商品

第4件商品iPhone：2000美元，1磅

	1	2	3	4
吉他	1500G	1500G	1500G	1500G
音响	1500G	1500G	1500G	3000S
笔记本电脑	1500G	1500G	2000L	3500L G
iPhone	2000I	3500G I	3500G I	*4000L I*

5件商品

第5件商品MP3：1000美元，1磅

	1	2	3	4
吉他	1500G	1500G	1500G	1500G
音响	1500G	1500G	1500G	3000S
笔记本电脑	1500G	1500G	2000L	3500L G
iPhone	2000I	3500G I	3500G I	4000L I
MP3	2000I	3500G I	3500G I	4000L I

1	`# 9.1 不偷`

行的排列顺序发生变化

行的排列顺序发生变化时，最终答案不变，即各行的排列顺序无关紧要。

	1	2	3	4
音响	-	-	-	3000S
笔记本电脑	-	-	2000L	3000S
吉他	1500G	1500G	2000L	3500G L

逐列填充网格可能会有影响

增加一件更小的商品

比如一条项链：1000美元，0.5磅。这需要将网格细化，每列最小刻度为0.5。

偷商品的一部分

动态规划没办法处理连续性问题，只能处理分立问题。这种情况可以用贪婪算法处理。（1）尽可能多的拿价值最高的商品，（2）如果拿光了，再尽可能多的拿价值次高的商品，以此类推。

旅游行程最优化

你有两天假期，旅游地点及时间如下

名胜	时间	评分
威斯敏斯特教堂	0.5天	7
环球剧场	0.5天	6
英国国家美术馆	1天	9
大英博物馆	2天	9
圣保罗大教堂	0.5天	8

如何确定旅游行程？绘制动态规划网格如下

	0.5	1	1.5	2
威斯敏斯特教堂W	7W	7W	7W	7W
环球剧场T	7W	13W T	13W T	13W T
英国国家美术馆A	7W	13W T	16W A	22W A T
大英博物馆	7W	13W T	16W A	22W A T
圣保罗大教堂S	8S	15W S	17S A	24W S A

旅游行程为：威斯敏斯特教堂->圣保罗大教堂->英国国家美术馆

处理相互依赖的情况

仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。

计算最终的解时不会涉及两个以上子背包

最多只需要合并两个子背包，即根本不会涉及两个以上的子背包。不过这些子背包可能又包含子背包。

最优解可能导致背包没装满

练习9.2

	1	2	3	4	5	6
水W	-	-	10W	10W	10W	10W
书B	3B	3B	10W	13BW	13BW	13BW
食物F	3B	9F	12FB	13BW	19FW	22FBW
夹克J	3B	9F	12FB	14JW	19FW	22FBW
相机C	6C	9CB	15CF	18CFB	20CJF	25CFW

应该带水、食物和相机

最长公共子串

费曼算法（滑稽）

将问题写下来
好好思考
将答案写下来

一个输错的单词hish，更像fish还是fosh？

	i	s	h
f	0	0	0
i	1	0	0
s	0	2	0
h	0	0	3

if word_a[i] == word_b[j]:
    cell[i][j] = cell[i-1][j-1] + 1
else:
    cell[i][j] = 0

最长公共子串：两个字符串中连续相同的部分。

最长公共子序列：两个字符串中都有的序列包含的字母数。

两者的区别是：子串要求在原字符串中是连续的，而子序列则只需保持相对顺序，并不要求连续。

	f	o	s	h
f	1	1	1	1
i	1	1	1	1
s	1	1	2	2
h	1	1	2	3

if word_a[i] == word_b[j]:
    cell[i][j] = cell[i-1][j-1] + 1
else:
    cell[i][j] = max(cell[i-1][j], cell[i][j-1])

练习9.3

	l	u	e
c	0	0	0
l	1	0	0
u	0	2	0
e	0	0	3
s	0	0	0

动态规划的实际应用

根据最长公共序列确定DNA链的相似性。
git diff指出两个文件的差异。
编辑距离（levenshtein distance）指出两个字符串的相似程度，使用了动态规划。编辑距离算法用于拼写检查，判断用户上传资料是否为盗版等。
Microsoft Word等的断字功能。

动态规划小结

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

10 K最近邻算法

要对东西进行分类时，可首先尝试K最近邻（k-nearest neighbours, KNN，k代表多个）算法。

创建推荐系统

为用户Priyanka创建一个电影推荐系统，这本质上是分类问题，将Priyanka归类到喜好相近的人群中，然后将这群人喜好的电影推荐给他就好了。

特征抽取

特征抽取意味着将物品转换为一系列可比较的数字。用户注册时，要求他们指出对各种电影的喜好程度。这样，对于每位用户都将获得一组数字。

	Priyanka	Justin	Morpheus
喜剧片	3	4	2
动作片	4	3	5
生活片	4	5	1
恐怖片	1	1	3
爱情片	4	5	1

毕达哥拉斯公式：\(\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+...}\)

Priyanka和Justin的距离为2，Priyanka和Morpheus的距离为\(\sqrt{24}\)。所以Priyanka喜好更接近Justin，以后可以将Justin喜欢的电影推荐给Priyanka。

'''
10.1 归一化
10.2 意见领袖权重大
'''

回归

如果不仅要向Priyanka推荐电影，还要预测她将给这部电影打多少分。先看下最近邻打多少分

Justin	5
Jc	4
Joet	4
Lance	5
Chris	3

求平均为4.2，这就是回归（regression）。KNN的两项基本工作——分类和回归。

分类就是编组。
回归就是预测结果（如数字）。

预测应该烤多少条面包，首先需要一组特征

天气指数1~5（1表示很糟，5表示很好）
是不是周末或节假日（是1，否0）
有没有活动（有1，无0）

还需要一些历史数据，记录各种不同日子里售出的面包数量。

第一列	第二列
A(5,1,0) = 300	B(3,1,1) = 225
C(1,1,0) = 75	D(4,0,1) = 200
E(4,0,0) = 150	F(2,0,0) = 50

今天时周末，天气不错，即(4,1,0)。使用KNN算法，其中K设为4。首先，找出今天的4个最近邻。LA=1，LB=\(\sqrt{2}\)，LC=3，LD=\(\sqrt{2}\)，LE=1，LF=\(\sqrt{5}\)。因此，4个最近邻为ABDE。求回归，即取平均为(300+225+200+150)/4=218.75条。这就是预测的今天应烤的面包数。

余弦相似度

余弦相似度（cosine similarity）不计算两个矢量的距离，而是比较它们的角度。更适合处理品味类似但打分保守程度不一致的情况。详见

挑选合适的特征

在挑选合适的特征方面，没有放之四海皆准的原则，必须要考虑多种需要考虑的因素。能否挑选合适的特征事关KNN算法的成败。

1	`# 10.3 太少了。经验规则：如果有N位用户，应考虑sqrt(N)个邻居。`

机器学习简介

机器学习旨在让计算机更聪明。创建推荐系统就是机器学习的一个例子。

OCR

OCR是指光学字符识别（optical character recognition）。语音识别和人脸识别也是用相同的理念。可使用KNN算法，

浏览大量的数字图像，将这些数字的特征提取出来。这一步称之为训练（training）
遇到新图像时，提取该图像的特征，再找出它的最近邻。

创建垃圾邮件过滤器

垃圾邮件过滤器使用一种简单算法——朴素贝叶斯分类器（Naive Bayes Classifier）。首先使用一些数据对这个分类器进行训练，即拿垃圾邮件和非垃圾邮件的主题喂食计算机。有新邮件时，分析主题中的每个单词再垃圾邮件中出现的概率。

预测股票市场

不好挑选合适的特征。几乎是难以完成的任务。

11 十种算法简介

树

二叉查找树（binary search tree）。对于其中的每个节点，左子节点的值都比它小，而右子节点的值都比它大。

在二叉查找树查找节点时，平均运行时间为O(log n)，但在最糟糕的情况下所需时间为O(n)。而在有序数组中查找时，最糟糕情况下也只有O(log n)。但是二叉查找树的插入和删除操作的速度快得多。但二叉查找树不能随机访问元素。

	数组	二叉查找树
查找	O(log n)	O(log n)
插入	O(n)	O(log n)
删除	O(n)	O(log n)

其他数据结构：B树，红黑树，堆，伸展树。

反向索引

反向索引（inverted index）常用于创建搜索引擎。创建一个散列表，将单词（键）映射到包含他的页面（值），搜索单词即可给出包含他的页面。

傅立叶变换

信号分析领域。

并行算法

并行算法设计起来很难，要确保它们能够正确地工作并实现期望的速度提升也很难。而且速度的提升并非线性的，其中的原因有两个。

并行性管理开销。任务的分配与合并也是需要时间的。
负载均衡。分配给每个内核的任务难度可能不一样。

要改善性能和可扩展性，并行算法可能是个不错的选择。

MapReduce

MapReduce是一种流行的分布式算法，可以通过流行的开源工具Apache Hadoop来使用它。

分布式算法非常适合用于在段时间内完成海量工作，其中的MapReduce基于两个简单的理念：映射（map）函数和归并（reduce）函数。

映射函数

1
2
3

arr1 = [1,2,3,4,5]
arr2 = map(lambda x: 2*x, arr1) # 数组元素翻倍
print(list(arr2)) # 转换为列表打印

1 2	`arr1 = # A list of URLs arr2 = map(download_page, arr1) # 下载页面存储在arr2中`

归并函数

归并是将一个数组转换为一个元素。

1 2	`arr1 = [1,2,3,4,5] reduce(lambda x,y: x+y, arr1) # 将所有元素相加`

布隆过滤器和HyperLogLog

布隆过滤器是一种概率型数据结构，它提供的答案有可能不对，但很可能是正确的。为判断网页是否已搜集过，可不使用散列表（占用空间大），而使用布隆过滤器使用散列表时，答案绝对可靠，而使用布隆过滤器时，答案却是很可能是正确的。

可能出现错报的情况，即Google可能指出“这个网站已搜集”，但实际上并没有搜集。
不可能出现漏报的情况，即如果布隆过滤器说“这个网站未搜集”，就肯定未搜集。

布隆过滤器的优点在于占用的存储空间很少。使用散列表时，必须存储Google搜集过的所有URL，但使用布隆过滤器时不用这样做。布隆过滤器非常适合用于不要求答案绝对准确的情况，前面所有的示例都是这样的。对bit.ly而言，这样说完全可行：“我们认为这个网站可能是恶意的，请倍加小心。”

HyperLogLog

HyperLogLog是一种类似于布隆过滤器的算法。HyperLogLog近似地计算集合中不同的元素数，与布隆过滤器一样，它不能给出准确的答案，但也八九不离十，而占用的内存空间却少得多。

SHA算法

比较文件

另一种散列函数是安全散列算法（secure hash algorithm，SHA）函数。给定一个字符串， SHA返回其散列值（哈希值）。可以使用SHA来判断两个文件是否相同，这在比较超大型文件时很有用。

检查密码

Google存储的并非密码，而是密码的SHA散列值！你输入密码时，Google计算其散列值，并将结果同其数据库中的散列值进行比较。这种散列算法是单向的。你可根据字符串计算出散列值。但你无法根据散列值推断出原始字符串。

SHA实际上是一系列算法： SHA-0、 SHA-1、 SHA-2和SHA-3。本书编写期间， SHA-0和SHA-1已被发现存在一些缺陷。如果你要使用SHA算法来计算密码的散列值，请使用SHA-2或SHA-3。当前，最安全的密码散列函数是bcrypt，但没有任何东西是万无一失的。

局部敏感的散列算法

SHA是局部不敏感的，即一个字符串，只改变其中一个字符，哈希值就完全不同。而Simhash是一种局部敏感的散列函数，即对字符串做细微的修改，其哈希值也只发生细微的改变。

Google使用Simhash来判断网页是否已搜集。
老师可以使用Simhash来判断学生的论文是否是从网上抄的。
Scribd允许用户上传文档或图书，以便与人分享，但不希望用户上传有版权的内容！这个网站可使用Simhash来检查上传的内容是否与小说《哈利·波特》类似，如果类似，就自动拒绝。

需要检查两项内容的相似程度时，Simhash很有用。

Diffie-Hellman密钥交换

Diffie-Hellman算法解决了如下两个问题。

双方无需知道加密算法。他们不必会面协商要使用的加密算法。
要破解加密的消息比登天还难。

Diffie-Hellman使用两个密钥：公钥和私钥。有人要向你发送消息时，他使用公钥对其进行加密。加密后的消息只有使用私钥才能解密。只要只有你知道私钥，就只有你才能解密消息！

类似算法还要RSA。

线性规划

线性规划用于在给定约束条件下最大限度地改善指定的指标。

线性规划使用Simplex算法

笔记

algorithm

本文作者: Shixin
本文链接: https://physxz.github.io/posts/10016/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

Linux系统下玩转51单片机上一篇

OpenCV项目实战下一篇

算法基础