算法简介
算法要么有速度，要么解决有趣的问题。
二分法
当有序的时候。就要想到二分法。
- 范围缩小到只包含一个元素
def binary_serach(arr, target):
left = 0
right = len(arr) - 1
while left <= right: # 缩减到只包含一个元素
mid = (left + right) / 2
if arr[mid] == item:
return mid
elif arr[mid] > item:
right = mid - 1
else:
left = mid + 1
return None
图算法编写跟踪用户的AI系统。
K最近邻算法编写推荐系统
NP完全问题。
Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题。
用穷举法得到答案，一个个检验下去才能得到答案
对数
对数运算是幂运算的逆运算
10^2= 100 log 10 100 = 2
2^3 = 8 log2 8 = 3
大O运行时间
O(log n)：对数时间。 二分查找
O(n)： 线性时间
O(n * log n) :快速排序
O(n^2): 选择排序
O(n !) ：旅行商问题
数组和链表 选择排序
数组：内存连续
链表：内存不需要连续。
递归
递归：代码简单，不容易理解。
要慢慢收敛，分俩个条件：
- 基线条件：函数啥时候停止
- 递归条件：函数啥时候调自己
快速排序
分而治之。 divide and conquer --递归式解决问题
1： 找出简单的基线条件
2： 如何缩小问题的规模，使其符合基线条件。
农场主分土地。均匀的分成方块，最大可分成的方块大小是多少。
拿当前较小的边为边长分割。剩余土地的继续。直到正好分割完毕。
def quicksork(arr):
# 基线条件
if len(arr) < 2:
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 quicksort(less) + [pivot] + quicksort(greater)
这种 更好理解。比起在原数组上向右扩大区域。就是浪费空间。
散列表
查找的速度为O(1)
散列函数
能把输入映射成一个数字。 同样的输入映射的数字一定一样。
散列冲突
输入是无限的。输出是有限的。可能32位或者64位，再大点128位。
好的散列函数生成的是均匀的。如果冲突。当前位置就存储成链表。
填装因子
当前散列表的元素 / 位置总数
填装因子大于0.7。就该调整了。
广度优先搜索
breadth-firsh-search . BFS
BFS可以找出俩样东西之间最短的距离。
- 计算最少走多少步获胜
- 拼写检查器，最少编辑多少个地方就可将错拼的单词改成正确的单词
- 人际关系找最近的医生
使用图来建立模型，通过BFS来解决问题。
图由节点和边组成的。
第一类问题：从A有到B的路径吗
第二类问题：从A到B最短的路径。
实现图
python就是暴力，用字典。
g = {}
g["you"] = ["alice", "bob", "claire"]
g["bob"] = ["anuj", "peggy"]
g["alice"] = ["peggy"]
g["claire"] = ["thom", "jonny"]
g["anuj"] = []
g["peggy"] = []
g["thom"] = []
g["jonny"] = []
实现算法
from collections import deque
s_q = deque()
s_q += g["you"]
s_d = []
s_d.append("you")
while s_q:
current_person = s_q.popleft()
if current_person in s_d:
continue
if current_persion[-1] == 'm':
print(f"{current_person} is a mango seller!")
return True
else:
s_q += g[current_person]
return False
迪克斯特拉算法
加权图
有最短路劲，但不一定是最快的。还有最快路劲。边有权。
1、 找出最便宜的节点。
2、 更新该节点的邻居的开销，如果有更快的，则更新邻居节点的开销。
3、 重复
只适用于有向无环图 directed acyclic graph .DAG ,不能有负权。
算法实现
g: 图
costs: 每个节点的开销。
parents: 最小开销的父节点
# 构造图模型
g = {}
g["start"] = {}
g["start"]["a"] = 6
g["start"]["b"] = 2
g["a"] = {}
g["a"]["fin"] = 1
g["b"] = {}
g["b"]["a"] = 3
g["b"]["fin"] = 5
g["fin"] = {}
infinity = float("inf")
processed = [] # 保存已经锁定的
costs = {}
costs["start"] = 0
for item in g["start"].keys():
costs[item] = g["start"][item]
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
lowest_node = find_lowest_cost_node(costs):
while node:
current_cost = costs[lowest_node]
for n in g[lowest_node].keys():
new_cost = current_cost + g[lowest_node][n]
if costs[n] > new_cost:
costs[n] = new_cost
parents[n] = lowest_node
processed.append(lowest_node)
lowest_node = find_lowest_cost_node(costs)
贪婪算法
如何处理不可能完成的任务
识别NP完全问题
近似算法得到NP完全问题的近似解
贪婪策略
教室调度问题
如何在这间教室上更多的课。
1）选出结束最早的课。
2）选出第一堂课结束后才开始的课。
贪婪算法：每步都选择局部最优解，最终得到就是全局最优解。
背包问题
包里只能装35磅的东西。如何能使包里装的东西最贵。
贪婪：直接装最贵的，依次装下一个能装下最贵的。
显然这个不是。证明贪婪算法是错误的，只需要举反例。
这个需要动态规划解决。
集合覆盖问题
广播节目需要50个州全部听到。决定哪些广播台播出。尽可能少的广播台。
每个广播台都有覆盖的州。
如何找出覆盖全美50个州最小广播台集合。
1）列出每个可能的广播台集合。 幂集 power set . 2^n 个。
2）在这些集合中选出覆盖全美50个州的最小集合。
没有任何算法可以快速的解决这个问题。
近似算法
1） 选出一个广播台。覆盖了最多的未覆盖的州，已覆盖了也没关系。
2） 重复第一步。直到覆盖了所有的州。
NP完全问题
为解决集合覆盖问题，必须计算每个可能的集合。
阶乘问题。需要计算所有的解。
如果能够判断出要解决的问题属于NP完全问题，就不需要寻找完美的解决方案。使用近似算法即可。
贪婪算法就是不错的近似算法。
动态规划
- 解决棘手问题，将问题分成小问题。并先着手解决小问题。
背包问题
先解决小背包的问题。在逐步解决原来的问题。
每个动态规划算法都从一个网格开始。从左到右。从上到下。
行为商品，列为包的容量
网格最初是空的。
值为在背包容量为当前列的大小的时候。可以装当前行及之前行的东西。最大的价值是多少。
填当前格的时候。要不要装当前行的和装当前行俩种选择。
当然还要判断能否装的下当前商品。
cell[i][j] = max(cell[i-1][j]), 当前商品价值 + cell[i-1][j - 当前商品重量]）
子问题必须是离散的。 不依赖其他子问题。动态规划才管用。
最长公共子串
如果用户拼写错误了。猜测他原本要输入的是什么单词。
HISH : FISH or VISTA
fosh : fish or fort
绘制网格
三个问题
1：单元格的值是什么
2：如何将这个问题划分为子问题
3：网格的坐标轴是什么
hish和fish最长公共子串是ish.
if word_a[i] == word_b[j]:
# 俩个字母相同
cell[i][j] = cell[i-1][j-1] + 1
else:
# 俩个字母不同：
cell[i][j] = 0
fosh和fish的最长公共子序列3（fsh）
if word_a[i] == word_b[j]:
# 如果俩个字母相同，那就+1
cell[i][j] = cell[i-1][j-1] + 1
else:
# 俩个不同，取 左和上 较大的一个
cell[i][j] = max(cell[i-1][j], cell[i][j-1])
K最近邻算法
- 使用K最近邻算法创建分类系统
- 特征抽取
- 回归，预测数值。
橙子还是柚子
看它的邻居，最近的三个邻居，如果橙子比柚子多，那么很可能是橙子。
k-nearest neighbours , KNN. 进行分类。
创建推荐系统
电影推荐系统
将用户转换为一组数子的方式。
然后计算用户之间的空间距离：毕达哥斯拉公式
还有使用余弦相似度的 cosine similarity
回归
不仅仅推荐电影，还要预测给电影大多少分。
分类是编组，回归就是预测结果，一个数字。
计算K近邻的平均值。 这就是回归。
挑选合适的特征
考虑各种各样的因素。别单调，
OCR
光学字符识别： optical character recognition
1): 浏览大量的数字图像，将这些数字的特征提取出来
2): 遇到新图像，提取该图像的特征，再找出它最近的邻居都是谁。
OCR提取线段、点和曲线等特征
创建垃圾邮件过滤器
使用的是--朴素贝叶斯分类器 Naive Bayes classifier
先要有数据进行训练。很多邮件已经被标注为 垃圾邮件和非垃圾邮件
收到主题为“collect your million dollars now”, 这是垃圾邮件吗？ 研究这个句子中的每个单词，看看它在垃圾邮件中出现的概率
机器学习的前提都是训练机器，喂数据。
Next Do What ？
树
二叉查找树 binary search tree 左子节点的值都比它小。右子节点都比它大。
反向索引
三个网页A: hi, there B：hi， adit , C: there we go
我们根据这些内容创建一个散列表。值为包含指定单词的页面。
hi: A,B
there: A,C
用户搜索 hi, 就可以返回A,B
一个散列表，将单词映射到包含它的页面，这种数据结构被称为 反向索引 inverted index
傅里叶变换
给它一杯沙，能告诉你其中包含哪些成分
给它一首歌曲，能够将其中的各种频率分离出来
并行算法
海量数据处理相关。 排序算法的速度大概是n * log n。为提高算法的速度。要在多个内核中并行地执行。
- 并行性管理开销： 如何分配到多个内核，如何合并结果
- 负载均衡： 让内核能够发挥自己最大的性能
MapReduce
分布式算法，算法在多台计算机上运行
映射 map 和 归并 reduce
布隆过滤器
判断一个东西是否已经存在。不需要100% 的正确性。数据量大。
布隆过滤器是一种概率型数据结构。 提供的答案有可能不对，但是很有可能是对的。
不会出现漏报的情况。如果没有，那么肯定没有。
SHA算法
散列函的结果是均匀分布的。局部不敏感。接收一个字符串，返回一个索引号。
可以用来比较文件。检查密码。
有时候又希望散列函数局部敏感。字符串只有细微的差别，那么生成的散列值也只存在细微的差别。比如检查小说是否盗版。
Diffie-Hellman密钥交换
如何对消息加密，只有收件人能看懂呢？
使用俩个密钥：公钥和私钥 。
使用公钥加密消息，只有对应的私钥才能解密。 私钥只有自己知道。所以，只有自己才能解密消息。
线性规划
在给定约束的条件下最大限度地改善指定的指标。
所有的图算法都是使用线性规划来实现的。。。
读后感
这本书写的感觉很实在。比java 好多了。
也提供了很多其他思路，比如快速排序，当然左神的在当前数组右扩左扩肯定是最优的，但是这里的实现就很 容易懂。。
动态规划和贪婪算法和左神讲的差不多哈哈。
人生苦短，要用python啊。
刻画了 动态规划，绘制表格，从小问题入手。大问题就自然而然解决了。
python里的图使用字典就可以构造。 当然java也可以。
只是字典这种模型就很容易理解，结构很清晰。
过年太影响计划了。。
关于算法，首推这本书。
挺讨厌刷题的啊啊啊啊啊啊啊啊。
3.1日晚。