算法图解学习
作为算法学习的入门书，这本书棒极了
本书用的log均为2为底
很多文本直接参考了知乎专栏 https://zhuanlan.zhihu.com/p/38488791
GPS使用图算法来计算前往目的地的最短路径，在6，7，8章介绍
1.2 二分查找
首先，查找不是排序
折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列
对半开，比楞查效率更高
对数是幂运算的逆运算
大前提是先按大小排好序
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 选择排序
运行时间O(n*1/2*n)
我觉得n(n+1)/2
# 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实现的就是快速排序
基线条件为 空或只包含一个元素（因为不需要排序）
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提供的散列表实现是字典（大括号）
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 防止重复
散列表与列表的最大差别在于：列表需要遍历才能查询，而散列表不需要（很明显散列表占用的资源更多）
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 实现算法
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 实现
# 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 集合覆盖问题
# 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完全问题：
- 元素较少时，算法的运行速度非常快，但是随着元素的增加，速度会变得非常慢；
- 涉及 所有组合 的问题通常是NP完成问题；
- 不能将问题分解为小问题，必须考虑各种可能的情况的问题，可能是NP完全问题；
- 如果问题涉及到序列且难以解决（旅行商问题中的城市序列），则可能是NP完全问题；
- 如果问题涉及到集合（如广播台集合）且难以解决，可能是NP完全问题；
- 如果问题可转换我集合覆盖问题或者旅行商问题，一定就是NP完全问题；
9 动态规划
大事化小，小事化无
还有一种被称作「动态规划」的思维方式可以帮我们解决问题 这种思维方式的核心在于，先解决子问题，再逐步解决大问题。这也导致「动态规划」思想适用于子问题都是离散的，即不依赖其他子问题的问题。
动态规划使用小贴士：
- 每种动态规划解决方案都设计网格；
- 单元格中的值通常是要优化的值；
- 每个单元格都是一个子问题
这个解答很棒！
动态规划只能拿和不拿整件商品，无法考虑拿走商品的一部分
可用于模糊搜索的寻找最长公共子串
10 K最邻近算法
余弦相似度？？ 取代 最近距离
本书对 KNN 也做了简单的介绍，KNN的合并观点如下
- KNN 用于分类和回归，需要考虑最近的邻居。
- 分类就是编组
- 回归就是预测结果
- 特征抽离意味着将物品转换为一系列可比较的数字。
- 能否挑选合适的特征事关KNN算法的成败
11 进一步的学习建议
读完本书，对算法总算有了一个入门的理解，当然算法还有很多值得深入学习的地方，以下是作者推荐的一些方向。
- 树
- 反向索引：搜索引擎的原理
- 傅里叶变换：傅里叶变换非常适合用于处理信号，可使用它来压缩音乐；
- 并行算法：速度提升并非线性的，并行性管理开销，负载均衡
- MapReduce：是一种流行的分布式算法，可通过流行的开源工具 Apache Hadoop 来使用；
- 布隆过滤器和 HyperLogLog：面对海量数据，找到键对于的值是一个挑战性的事情，布隆过滤器是一种概率性的数据结构，答案可能不对也可能是正确的；其优点在于占用的存储空间很小
- SHA 算法（secure hash algorithm）安全散列函数，可用于对比文件，检查密码
- 局部敏感的散列算法，让攻击者无法通过比较散列值是否类似来破解密码
- Diffie-Hellman 密钥交换
- 线性规划：用于在给定约束条件下最大限度的改善制定的指标
Diffie-Hellman 密钥交换
其继任者为RSA，简单易懂的公钥，私钥加密方案