Algorithms Lessons From MIT

2020/01/29

Tags:

在推上看到的这个课程 Introduction to Algorithms,虽然是 2011 年的,但是基础的东西还是比较稳定的,刚好补习一下基础知识,做点笔记。

Peak finding

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

Models of Computation, Document Distance

文档距离公式:

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

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

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

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

Insertion Sort, Merge Sort

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

Heaps and Heap Sort

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

Binary Search Trees, BST Sort, AVL trees, AVL Sort

各种树,copy 自网络…

二叉查找树 Binary Search Trees

平衡二叉搜索树 AVL

B树

B树也叫平衡树,也叫作B-树,英文为Blance-Tree。是一种多路平衡树。

一个m阶的B树规定了: 1.根结点至少有两个子女。 2.每个中间节点都包含k-1个元素和k个孩子,其中 m/2 <= k <= m 。 3.每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m。 4.所有的叶子结点都位于同一层。 5.每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

B+树:

B+树每个非叶子结点存放的元素只用于索引作用,所有数据保存在叶子结点。一个m阶的B+树规定了:

1.有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。 2.所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。 3.所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。

红黑树

红黑树也叫RB树,RB-Tree。是一种自平衡的二叉查找树,它的节点的颜色为红色和黑色。它不严格控制左、右子树高度或节点数之差小于等于1。也是一种解决二叉查找树极端情况的数据结构。

1.节点是红色或黑色。 2.根节点是黑色。 3.每个叶子节点都是黑色的空节点(NIL节点)。 4 每个红色节点的两个子节点都是黑色。也就是说从每个叶子到根的所有路径上不能有两个连续的红色节点)。 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树在查找方面和AVL树操作几乎相同。但是在插入和删除操作上,AVL树每次插入删除会进行大量的平衡度计算,红黑树是牺牲了严格的高度平衡的优越条件为代价,它只要求部分地达到平衡要求,结合变色,降低了对旋转的要求,从而提高了性能。红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外,由于它的设计,任何不平衡都会在三次旋转之内解决。

相比于BST,因为红黑树可以能确保树的最长路径不大于两倍的最短路径的长度,所以可以看出它的查找效果是有最低保证的。在最坏的情况下也可以保证O(logN)的,这是要好于二叉查找树的。因为二叉查找树最坏情况可以让查找达到O(N)。

红黑树的算法时间复杂度和AVL相同,但统计性能比AVL树更高,所以在插入和删除中所做的后期维护操作肯定会比红黑树要耗时好多,但是他们的查找效率都是O(logN),所以红黑树应用还是高于AVL树的. 实际上插入 AVL 树和红黑树的速度取决于你所插入的数据.如果你的数据分布较好,则比较宜于采用 AVL树(例如随机产生系列数),但是如果你想处理比较杂乱的情况,则红黑树是比较快的。

Counting Sort, Radix Sort, Lower Bounds for Sorting

Hashing with Chaining

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

1
2
3
4
>>> 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的随机数。

Table Doubling, Karp-Rabin

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

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

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

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

dict 数据结构包含两个 table ht[2],和一个 rehashidx。通常情况下,ht2 对应的 table 是空的。只有 ht1 有数据。此时 rehashidx 的值是 -1。当负载因子超过阈值之后,会进行 rehash。先预申请 ht2 的空间,然后递增 rehashidx 为当前 rehash 进度的 key,对于小于等于这个 idx 的 key,插入和查找都去新的 ht2 操作。直到 rehash 完毕,会把 ht2 改为 ht1,同时放一个空的 ht2。

Redis skiplist 的实现方法

Open Addressing, Cryptographic Hashing

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

Integer Arithmetic, Karatsuba Multiplication & Square Roots, Newton's Method

大数的算术运算

Breadth-First Search (BFS) & Depth-First Search (DFS), Topological Sort

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

图的表示:

  1. 使用数组的方法,adj[v] = [] 每个节点 v 可到达的邻居节点数组/链表。

  2. 使用对象,v.neighbors = adj[v]

  3. 使用函数,adj(v), v.neighbors() 都是函数,这样节省空间

BFS 遍历实现思路:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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 遍历的反向输出可以排序,在完成一个节点的遍历之后,这个节点就是第一个需要完成的。

Single-source shortest paths problem & Dijkstra & Bellman-Ford & Speeding up Dijkstra

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

Dynamic programming I: Fibonacci, shortest paths & Dynamic Programming II: Text Justification, Blackjack

动态规划 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

Comments