作为算法学习的入门书，这本书棒极了

本书用的log均为2为底

很多文本直接参考了知乎专栏 https://zhuanlan.zhihu.com/p/38488791

GPS使用图算法来计算前往目的地的最短路径，在6，7，8章介绍

1.2 二分查找

首先，查找不是排序

折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

对半开，比楞查效率更高

对数是幂运算的逆运算

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
大前提是先按大小排好序
def binary_search(list, item):
  # low and high keep track of which part of the list you'll search in.
  low = 0
  high = len(list) - 1

  # While you haven't narrowed it down to one element ...
  while low <= high:
    # ... check the middle element
    mid = (low + high) // 2
    guess = list[mid]
    # Found the item.
    if guess == item:
      return mid
    # The guess was too high.
    if guess > item:
      high = mid - 1
    # The guess was too low.
    else:
      low = mid + 1

  # Item doesn't exist
  return None

my_list = [2, 3, 5, 7, 11,13]
print(binary_search(my_list, 13)) # => 1
# 返回所在位置
# 'None' means nil in Python. We use to indicate that the item wasn't found.
print(binary_search(my_list, -1)) # => None

1.3大O表示法

O 是 Operation 的简写

并非以秒为单位，基准值并不确定

例如,假设列表包含 n 个元素。简单查找需要检查每个元素,因此需要执行 n 次操作。使用大O表示法, 这个运行时间为O(n)

通过比较操作数，指出算法运行的增速

在二分查找中，最多需要检查log n个元素

时间复杂度：O（log2n）

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

O(log n),对数时间

O(n),线性时间

O(n*log n),快速排序

O(n^2),选择排序，冒泡排序

O(n!),旅行商问题

大O表示法忽略1/2这样的常数

算法常常和数据结构挂钩。在介绍数据结构之前，我们需要先理解内存的工作原理，这样有助于我们理解数据结构。

2 选择排序

2.2 数组和链表

2.2.2 数组

要读取链表最后一个元素时，必须先从第一个元素开始读起

2.2.4 在中间插入

链表插入更简单，数组插入时要把后面的元素向后移

2.2.5 删除

链表修改地址即可

数组在删除元素后，将后面的元素向前移

数组支持随机访问

一种特殊的数据：链表数组

这个数组包含26个元素，每个元素指向一个链表

2.3 选择排序

1
运行时间O(n*1/2*n)

我觉得n(n+1)/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Finds the smallest value in an array
def findSmallest(arr):
  # Stores the smallest value
  smallest = arr[0]
  # Stores the index of the smallest value
  smallest_index = 0
  for i in range(1, len(arr)):
    if arr[i] < smallest:
      smallest_index = i
      smallest = arr[i]      
  return smallest_index

# Sort array
def selectionSort(arr):
  newArr = []
  for i in range(len(arr)):
      # Finds the smallest element in the array and adds it to the new array
      smallest = findSmallest(arr)
      newArr.append(arr.pop(smallest))
  return newArr

print(selectionSort([5, 3, 6, 2, 10]))

会有警告，i没有使用上，实际情况是i只用来循环

(C语言版本写的不好，原数列没有删掉，抽出的数用一个远大于数组的数取代，大O表示法应该是n的n次方)

3 递归

就是自己调用自己

“如果使用循环，程序性能可能更高；

如果使用递归，程序可能更容易理解”

3.2 基线条件和递归条件

递归条件：使函数调用自己的条件

基线条件：使函数不调用自己的条件

3.3 栈

后进先出，内存的一种储存方式

「栈」是一种先入后出（FILO）简单的数据结构。「调用栈」是计算机在内部使用的栈。当调用一个函数时，计算机会把函数调用所涉及到的所有变量都存在内存中。如果函数中继续调用函数，计算机会为第二个函数页分配内存并存在第一个函数上方。当第二个函数执行完时，会再回到第一个函数的内存处。

3.3.1 调用栈

所有函数调用都进入调用栈

写在函数里面的函数在最上层

即调用一个另函数时，当前函数暂停并处在未完成的状态

这个栈用于存储多个函数的变量，被称为调用栈

3.3.2 递归调用栈

递归函数也使用调用栈，所以迭代过多会造成堆栈溢出

4 快速排序

4.1 分而治之

一种著名的递归式问题解决方案

第一，找出基线条件，这种条件尽可能简单

第二，不断将问题分解，直到符合基线条件

递归一定要记录状态吗？？

4.2 快速排序

C语言标准库中的qsort实现的就是快速排序

基线条件为 空或只包含一个元素（因为不需要排序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def quicksort(array):
  if len(array) < 2:
    # base case, arrays with 0 or 1 element are already "sorted"
    return array
  else:
    # recursive case
    pivot = array[0]
    # sub-array of all the elements less than the pivot
    less = [i for i in array[1:] if i <= pivot]
    # 这是什么操作（python还有这种写法？）
    # 从1开始，往后循环
    # sub-array of all the elements greater than the pivot
    greater = [i for i in array[1:] if i > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3, 8]))

找基准值——分区——缩小规模到两个或一个数

4.3 再谈大O排序法

选择排序的时间为O(n^2)

而合并排序的时间为O(n logn)

快速排序在最坏情况下时间为O(n^2)

平均情况为O(n logn)

4.3.1 比较合并排序与快速排序

大O表示法不考虑常量（单位运行时间）

实际上，快速查找遇上平均情况的可能性比最糟情况要高很多

因为除非每次调动都不移动（或大部分前面不移动），都属于平均情况

快速查找的常量比合并排序+二分查找要低

4.3.2 平均情况和最糟情况

快速排序最坏的情况是初始序列已经有序，第1趟排序经过n-1次比较后，将第1个元素仍然定在原来的位置上，并得到一个长度为n-1的子序列；第2趟排序经过n-2次比较后，将第2个元素确定在它原来的位置上，又得到一个长度为n-2的子序列；以此类推，最终总的比较次数：
C(n) = (n-1) + (n-2) + … + 1 = n(n-1)/2
最坏的情况下，快速排序的时间复杂度为O(n^2)

所以，随机选择一个数作为基准值，一般都是平均时长

是分而治之的典范

5 散列表

最有用的数据结构之一

在编程语言中，存在另外一种和数组不同的复杂数据结构，比如JavaScript中的对象，或 Python 中的 字典。对应到计算机的存储上，它们可能可以对应为 散列表

哈希表又称散列表

5.1 散列函数

必须一一对应，且是确定关系

最理想的情况是，不同输入得到不同数字

散列表=散列函数+数组？？？

包含额外逻辑的数据结构？？

数组和函数直接映射到内存，而散列表使用散列函数确定函数的储存位置

Python提供的散列表实现是字典（大括号）

1
2
3
book = {"apple": 0.67, "milk": 1.49, "avocado": 1.49}
book["Lisa"] = 100
print(book)

（而C没有提供实例）

散列表将键映射到值

5.2 应用案例

5.2.1 将散列表用于查找

散列表是提供DNS解析的一种方式

5.2.2 防止重复

散列表与列表的最大差别在于：列表需要遍历才能查询，而散列表不需要（很明显散列表占用的资源更多）

1
2
3
4
5
6
7
8
9
10
11
12
voted = {}
def check_voter(name):
  if voted.get(name): 
    print("kick them out!")
  else:
    voted[name] = True
    print("let them vote!")

check_voter("tom")
check_voter("mike")
check_voter("mike")

5.2.3 将散列表用作缓存

5.3 冲突

即一对一映射中，另外一边映射的是链表

最理想的情况是：

散列函数将键均匀映射到散列表的不同位置

5.4 性能

如何选择一个好的散列函数？

数列表的平均运行为常量时间（简单查找是线性时间，二分查找是对数时间）

最糟情况是O(n) （为什么？目前没有找到原因？）

5.4.1 填装因子

填装因子=散列表包含的元素数/位置总数

填装因子越低，发生冲突的可能性越低，散列表性能越好

填装因子超过0.7就建议调整长度

良好的散列函数让数组中的值呈均匀分布，不过我们不用担心该如何才能构造好的散列函数，著名的SHA 函数，就可用作散列函数

6 广度优先搜索

数据结构图创建网络模型

拓扑排序，指出节点的依赖关系

6.1 图简介

将现实描绘成点线图

解决最短路径的算法被称为广度优先搜索

6.2 图是什么

图由节点（node）和边（edge）组成，它模拟一组连接。一个节点可能与众多节点直接相连，这些节点被称为邻居。有向图指的是节点之间单向连接，无向图指的是节点直接双向连接。

图用于仿真不同的东西是如何相连的

在编程语言中，我们可以用散列表来抽象表示图

6.3 广度优先搜索

广度优先搜索可解答两类问题：

第一，两个节点间存不存在路径

第二，两个节点间哪条路径最短

6.3.2 队列

即堆栈中的堆（先进先出）（FIFO）

队列的工作原理和现实生活中的队列完全相同，可类比为在公交车前排队，队列只支持两种操作：入队 和 出队。
队列是一种先进先出的（FIFO）数据结构。

FIFO=First In First Out

6.4 实现图

通过散列表实现，用表来实现图

散列表模拟图
散列表是一种用来模拟图的数据结构（？？？）

6.5 实现算法

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
from collections import deque

def person_is_seller(name):
      return name[-1] == 'm'

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 search(name):
    search_queue = deque() #定义其为队列
    search_queue += graph[name]
    # This array is how you keep track of which people you've searched before.
    searched = []
    while search_queue:
        person = search_queue.popleft()
        # Only search this person if you haven't already searched them.
        if person not in searched:
            if person_is_seller(person):
                print(person + " is a mango seller!")
                return True
            else:
                search_queue += graph[person]
                # Marks this person as searched
                searched.append(person)
    return False

search("you")

全局变量定义时，无视顺序

但字典里的键是唯一的，理论上是不会重复的

如果一个人为同一级两个人的好友，则需要一个表记录下已经登记过人，否则就会导致无限循环

运行时间至少是O（边数）

再算上队列检查时间O（人数）

所以广度优先搜索的运行时间为O（边数+人数）

如果任务A依赖任务B，在列表中任务A就必须在任务B后面

这被称为拓扑排序

只能往下指的图，被称作树

7 狄克斯特拉算法

引入加权图

环会使狄克斯特拉算法失效？？

最短路径不一定是最快路径，广度优先只能解决最短路径，而狄克斯特拉算法则可以解决这个问题，找出总权重最小的路径

找到图中最便宜的节点，并确保没有到该节点更便宜的路径

7.1 使用狄克斯特拉算法

第一，找出最短时间内能前往的节点，终点时间先设为无限

第二，对于该节点的邻居，检查是否有前往他们的更短路径，如果有则更新开销

第三，重复这一过程

第四，计算最终路径

我认为关键是对所有路径使用该算法

7.2 术语

狄克斯特拉算法只适用于有向无环图

其实应该是正权重有环图，环会因为权重被抛弃？？

7.3 换钢琴

7.4 负权边

负权边不能使用狄克斯特拉算法

因为狄克斯特拉算法有这样的假设：

对于处理过的节点，没有前往该节点的更新路径

7.5 实现

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
# the graph
# 用于确定父连接
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"] = {}

# the costs table
# 用于初始化
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

# the parents table
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
    # Go through each node.
    for node in costs:
        cost = costs[node]
        # If it's the lowest cost so far and hasn't been processed yet...
        if cost < lowest_cost and node not in processed:
            # ... set it as the new lowest-cost node.
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

# Find the lowest-cost node that you haven't processed yet.
node = find_lowest_cost_node(costs)
# If you've processed all the nodes, this while loop is done.
while node is not None:
    cost = costs[node]
    # Go through all the neighbors of this node.
    neighbors = graph[node]
    for n in neighbors.keys():
        new_cost = cost + neighbors[n]
        # If it's cheaper to get to this neighbor by going through this node...
        if costs[n] > new_cost:
            # ... update the cost for this node.
            costs[n] = new_cost
            # This node becomes the new parent for this neighbor.
            parents[n] = node
    # Mark the node as processed.
    processed.append(node)
    # Find the next node to process, and loop.
    node = find_lowest_cost_node(costs)

print("Cost from the start to each node:")
print(costs)


首先，需要3个散列表

第一个表储存节点的邻居

第二个表储存每个节点的开销

开销指的是从起点出发前往该节点所需要的时间

由于不知道终点要多久，先设为无穷大

python中的inf为无穷大

如果图中包含负权边

7.6 小结

如果图中包含负权边，使用贝尔曼-福德算法

8 贪婪算法

寻找近似解，处理没有快速算法得问题

8.1 教室调度问题

贪婪算法即是每步都采用最优解

8.2 背包问题

贪婪算法不一定是最优解，但应当与最优解相近

8.3 集合覆盖问题

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
# You pass an array in, and it gets converted to a set.
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()
#   第一遍时ktwo因为长度与kone的范围一样而没被纳入
while states_needed: #在遍历中，直到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

  states_needed -= states_covered
  final_stations.add(best_station)

print(final_stations)

近似算法

贪婪算法即是一种近似算法

准备工作-计算答案-集合处理

其判断优劣的方法是：

1.速度有多快

2.得到近似解与最优解的接近程度

完美是优秀的敌人。有时候，你只需要找一个能够大致解决问题的算法，此时贪婪算法正好可派上用场，它们的实现很容易，得到的结果又与正确结果接近。这时候采用的算法又被称作近似算法。

快速排序应该是近似算法????

8.4 NP完全问题

如何识别NP完全问题

以下是NP完成问题的一些特点，可以帮我我们识别NP完全问题：

  1. 元素较少时，算法的运行速度非常快，但是随着元素的增加，速度会变得非常慢；
  2. 涉及 所有组合 的问题通常是NP完成问题；
  3. 不能将问题分解为小问题，必须考虑各种可能的情况的问题，可能是NP完全问题；
  4. 如果问题涉及到序列且难以解决（旅行商问题中的城市序列），则可能是NP完全问题；
  5. 如果问题涉及到集合（如广播台集合）且难以解决，可能是NP完全问题；
  6. 如果问题可转换我集合覆盖问题或者旅行商问题，一定就是NP完全问题；

9 动态规划

大事化小，小事化无

还有一种被称作「动态规划」的思维方式可以帮我们解决问题
这种思维方式的核心在于，先解决子问题，再逐步解决大问题。这也导致「动态规划」思想适用于子问题都是离散的，即不依赖其他子问题的问题。

动态规划使用小贴士：

  • 每种动态规划解决方案都设计网格；
  • 单元格中的值通常是要优化的值；
  • 每个单元格都是一个子问题

附：什么是动态规划？动态规划的意义是什么？—知乎讨论

这个解答很棒！

动态规划只能拿和不拿整件商品，无法考虑拿走商品的一部分

可用于模糊搜索的寻找最长公共子串

10 K最邻近算法

余弦相似度？？ 取代 最近距离

本书对 KNN 也做了简单的介绍，KNN的合并观点如下

  • KNN 用于分类和回归，需要考虑最近的邻居。
  • 分类就是编组
  • 回归就是预测结果
  • 特征抽离意味着将物品转换为一系列可比较的数字。
  • 能否挑选合适的特征事关KNN算法的成败

11 进一步的学习建议

读完本书，对算法总算有了一个入门的理解，当然算法还有很多值得深入学习的地方，以下是作者推荐的一些方向。

  • 树
  • 反向索引：搜索引擎的原理
  • 傅里叶变换：傅里叶变换非常适合用于处理信号，可使用它来压缩音乐；
  • 并行算法：速度提升并非线性的，并行性管理开销，负载均衡
  • MapReduce：是一种流行的分布式算法，可通过流行的开源工具 Apache Hadoop 来使用；
  • 布隆过滤器和 HyperLogLog：面对海量数据，找到键对于的值是一个挑战性的事情，布隆过滤器是一种概率性的数据结构，答案可能不对也可能是正确的；其优点在于占用的存储空间很小
  • SHA 算法（secure hash algorithm）安全散列函数，可用于对比文件，检查密码
  • 局部敏感的散列算法，让攻击者无法通过比较散列值是否类似来破解密码
  • Diffie-Hellman 密钥交换
  • 线性规划：用于在给定约束条件下最大限度的改善制定的指标

Diffie-Hellman 密钥交换

其继任者为RSA，简单易懂的公钥，私钥加密方案