Algorithms Lessons From MIT

从头一个一个顺序找，是 O(n) 复杂度。也可以用二分，从中间开始找，然后递归，复杂度是 O(log(n)) 。

• L.append(x): O(1)
• L = L1 + L2: O(1)
• len(L): O(1)
• L.sort(): O(nlog(n)) 还和比较的复杂度有关系
• val in L: O(n)
• D[key]=val: O(1)
• key in D: O(1) 还取决于有没有冲突

文档距离公式：

d(D1, D2) = D1*D2 = ∑D1[W]*D2[W]

只考虑相同词出现的次数，这样文字多的会打分比较多，文字少的打分少，这个公式和文章规模没关系。所以修正下，除以他们的长度，就是

d(D1, D2) = D1*D2 = ∑(D1[W]*D2[W]/|D1|*|D2|)

这个就是计算两个向量的夹角，夹角越小表示两个越接近。

• 插入排序：顺序检查每个元素，和前面的比较，如果比前面的小，那就和前面的交换。如果发生了交换，那需要递归和更前面的比较，直到没有交换。继续检查下一个元素。复杂度是 O(n^2)。
• 插入排序优化：需要和前面发生交换的时候，因为前面都是排好序的，所以可以使用二分找到合适的位置，而不用一个一个找。复杂度是 O(nlog(n))。
• 归并排序：归并需要是排序好的数组，但是可以通过拆分，把原始数据拆分成2个未排序数组，然后递归继续拆分，直到两个数组只有一个元素，比较之后就可以归并成一个有序数组，递归返回就可以完成排序。复杂度 O(nlog(n))

递归算法的复杂度计算思路，T(n)=2T(n/2)+cx，取决于那个 x

• 如果 x 是 n ，每层递归都是 n，这样计算量是分布到每层的，层数是 log(n)，那就是 nlog(n)。
• 如果 x 是 1 ，那第一层是 c，第二层是 2c…. 都是常数，只有第 n 层是 cn 值得考虑，所以复杂度就是 n。
• 如果 x 是 n^2，那第一层是 cn^2，第二层是 cn^2/2…. 因为 1+1/2+1/4 < 2 这样后面的层就不用考虑了，只考虑第一层就行，所以复杂度就是 n^2。

• 堆：大顶堆，小顶堆，其他的。
• 堆排：先建一个小顶堆，可以得到最小值，拿掉最小值，重新递归建堆，拿掉最小值。建堆复杂度是 n，排序重建堆的复杂度是 nlog(n)，总的是 nlog(n)。

建堆复杂度的直觉是 nlog(n)（每个 max_heapfy 是 logn，需要循环 n 次。不过视频里面做了计算，叶子往上一层有 n/4 节点，每个节点需要 O(1) 交换，再往上一层有 n/8 节点，每个节点最多需要 O(2)，这样越往上节点越少，每个节点可能需要做的交换越多，整体算下来是个 cn，所以是 n。

各种树，copy 自网络…

• 对于小的正整数，把他们直接作为数组下标放到数组里面，相同的直接把 val 加一，这样直接输出所有不为空的数组元素(要考虑个数)就是排序结果了。
• 对于比较大的整数，可以把数做一个分解，比如简单的，按照 10 的倍数（也可以是别的倍数），先按照个位把数分到不同的数组元素里面，每个元素对应一个数组，包含了个位相同的多个数字。然后递归按照十位排序。这样实际就是对于只有个位的数，那第一轮排序结果就是最终结果了。对于两位的，那就第二轮排完就是结果了。一轮一轮下去，注意排第二轮的时候对于一位数要保持他们的顺序。

python 2(Python 2.7.16 (default, Nov 9 2019, 05:55:08) ) 里面一个 hash 冲突的例子。

>>> hash('\0B')
64
>>> hash('\0\0C')
64

对于 key -> item ，如果 key 都是整数，那就可以使用一个数组来存放这些数据，这样查找是 O(1) 复杂度。但是这样存在两个问题。

1. key 必须是正整数。
2. key 可能会很大，占用很多空间。

针对这两个问题解决方法：

1. 对于不是正整数的 key 先 prehash 到正整数。这样有一个 map 的过程，例如可以返回对象在内存里面的地址，或者其他映射方法。
2. 合理的减少 key 的取值空间，比如当你最多只有 20 个元素的时候没必要弄个一千万的空间出来。

冲突的解决方法：

1. 使用链表：对于 key 冲突，把 item 使用链表放到这个 key 对应的位置，这个时候查找会退化成 O(k)，k 是 hash 表的负载因子。
2. 开放地址：后面课程讲。

hash 函数实现方法：

1. 除法求余：h(k) = k mod m, m 是质数，但是不要太接近 2 或者 10 的指数倍。
2. 乘法：h(k) = [(a·k) mod 2^w] >> (w−r)，乘法和按位操作比除法速度快。
3. 通用的方法：h(k) = [(ak+b) mod p]，p 是质数，ab 是小于p的随机数。

hash table 的大小 m，和实际存放的数据量 n，负载因子 n/m 变大或者缩小到一定程度的时候就需要考虑增加或者缩小 m。

• 负载因子太大查询将不再是 O(1)
• 负载因子太小，会浪费很多空间

负载因子增加到一定大小的时候，可以通过 table doubling 的方法增加 table 的大小：

• 2x 增加，可以保证 amortized cost 是 O(n) 的，虽然有部分操作是线性的，但是类似平均操作复杂度是 O(1)
• 一般运行时会有大量操作，这样会比较关心总的操作时间，而不纠结某一个
• 也可以使用类似 redis 的实现方法，不要一次迁移到新表，每次读写的时候操作几个 key，直到全部的 key 都迁移完毕。这样可以把那些耗时的 rehash 操作分布到很多操作里面。

负载因子小到一定程度的时候，可以缩小 table 的大小：

• m < n/4 当表内数据量小于 1/4 的时候，把表缩成 m/2 大小。

子字符串查找，从 t 里面找到是否包含 s

• 使用双重循环，每次滑动从 t 里面取 s 长度的字串和 s 的每一个字符比较，看是否 match。复杂度是 O(|s|*(|t| - |s|)) = O(|s|*|t|) 如果 s 比较长，这个算法就比较慢了。
• Karp-Rabin 算法是通过比较 hash 值来看是否匹配。这样只要 hash 方法的复杂度小于 O(|s|) 就比上面的方法复杂度降低了。
• 计算 hash 值的时候，可以通过映射字符到数字，然后改为整数计算和比较，这样是 O(1) 复杂度，和字串长度无关了。主要思路是每次计算只需要考虑原来头部和新增尾部的字符就可以了，中间部分不用重复循环计算。

Open Addressing 开放地址法主要思路是

• 不使用链表
• 遇到插入的时候遇到冲突，那么用一个新的 hash 函数再次 hash 看存那里，这样循环直到找到一个合适的位置。
• 具体的探测可用地址的方法有简单的顺序线性探测，平方探测，伪随机探测等等，或者 double hashing。
• 删除的时候，把被删除的位置放一个 delete 标记，而不是 None，否则查找的时候会出错。插入的时候对 delete 标记和 None 做相同处理即可，可以复用空间。
• 线性探测会导致 clustering，导致存放数据不均衡。平方探测可能会导致不能探测到全部的空间。
• 要保持负载因子不要太大，否则探测次数会变大。

大数的算术运算

广度优先搜索(BFS) 和深度优先搜索(DFS)。

• BFS 遍历是一层一层依次往下遍历。
• DFS 遍历是优先往一个节点深度遍历，遇到结束返回上层继续遍历子节点。

图的表示：

1. 使用数组的方法，adj[v] = [] 每个节点 v 可到达的邻居节点数组/链表。
2. 使用对象，v.neighbors = adj[v]
3. 使用函数，adj(v), v.neighbors() 都是函数，这样节省空间

BFS 遍历实现思路：

BFS (V,Adj,s):
    level ={s:0}
    parent ={s:None}
    i= 1
    frontier= [s]# previous level,i−1
    while frontier:
        next = [] # next level,i
        for u in frontier:
            for v in Adj[u]:
                if v not in level:# not yet seen
                    level[v] =i #===level[u] + 1
                    parent[v] =u
                    next.append(v)
        frontier = next
        i+=1

也可以使用队列实现:

• 将根节点放入队列
• 从队列里面取一个，将他的子节点放到队列里面
• 重复上面步骤，直到队列为空

BFS 算法可以找到两个节点之间的最短路径，就是反向从目标节点根据 parent 找回根节点。

• 将根节点入栈
• 查看栈顶，将他的一个未处理过子节点入栈
• 重复上面步骤，直到没有子节点
• 出栈顶部节点，重复上面步骤处理其他未处理子节点

拓扑排序可以解决任务依赖问题，有向无环图(DAG, Directed Acyclic Graph)。通过 DFS 遍历的反向输出可以排序，在完成一个节点的遍历之后，这个节点就是第一个需要完成的。

字面翻译是单源最短路径问题，都是些寻路问题。

动态规划 DP =~ 总结就是把大问题切分成小问题，通过递归遍历再加对递归的结果记忆来解决问题的思路。

比如斐波那契数列计算， fib(n) = fib(n-1) + fib(n-2) 如果单纯的递归，那复杂度大于 O(2^n/2)。但是实际是有部分重复计算的，记忆上次的计算结果，每个数字只需要计算一次就可以，这样复杂度可以降到 O(n)。

5 Easy Steps to Dynamic Programming

1. define subproblemscount # subproblems
2. guess (part of solution)count # choices
3. relate subproblem solutions compute time/subproblem
4. recurse + memoizetime = time/subproblem · #sub-problems OR build DP table bottom-upcheck subproblems acyclic/topological order
5. solve original problem: = a subproblemOR by combining subproblem solutions=⇒extra tim