wd and cc

— Happy every day

Algorithms Lessons From MIT

Posted at — Jan 29, 2020

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

Peak finding

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

Models of Computation, Document Distance

  • 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|)

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

Insertion Sort, Merge Sort

  • 插入排序:顺序检查每个元素,和前面的比较,如果比前面的小,那就和前面的交换。如果发生了交换,那需要递归和更前面的比较,直到没有交换。继续检查下一个元素。复杂度是 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。

Heaps and Heap Sort

  • 堆:大顶堆,小顶堆,其他的。

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

建堆复杂度的直觉是 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

  • 左结点小于根节点,右结点大于根节点的一种排序树,也叫二叉搜索树。

  • 比普通树查找更快,查找、插入、删除的时间复杂度为O(logN)。但是二叉查找树有一种极端的情况,就是会变成一种线性链表似的结构。此时时间复杂度就变味了O(N),为了解决这种情况,出现了二叉平衡树。

平衡二叉搜索树 AVL

  • AVL 树也规定了左结点小于根节点,右结点大于根节点。并且还规定了左子树和右子树的高度差不得超过1。这样保证了它不会成为线性的链表。AVL树的查找稳定,查找、插入、删除的时间复杂度都为O(logN),但是由于要维持自身的平衡,所以进行插入和删除结点操作的时候,需要对结点进行频繁的旋转。

  • 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树每一层存放了更多的节点,由AVL树的“瘦高”变成了“矮胖”。可以相对减少磁盘IO的次数。MongoDB的索引就是用B树实现的。

  • B树也是一种自平衡的树,在进行插入和删除操作时也需要对结点进行旋转等操作。

  • 不过,B树的查找不稳定,最好的情况就是在根节点查到了,最坏的情况就是在叶子结点查到。另外,B树在遍历方面比较麻烦,由于需要进行中序遍历,所以也会进行一定数量的磁盘IO。为了解决这些问题,出现了B+树。

B+树:

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

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

  • 因为非叶子结点中存放的元素不存放数据,所以每一层可以容纳更多元素,也就是磁盘中的每一页可以存放更多元素。这样在查找时,磁盘IO的次数也会减少。

  • 另外,B+树的查找稳定,因为所有的数据都在叶子结点。每个叶子结点也通过指针指向构成了一种链表结构,所以遍历数据也会简单很多。

  • B+树的插入和删除和B树类似。

红黑树

红黑树也叫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

  • 对于小的正整数,把他们直接作为数组下标放到数组里面,相同的直接把 val 加一,这样直接输出所有不为空的数组元素(要考虑个数)就是排序结果了。

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

Hashing with Chaining

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的随机数。

Table Doubling, Karp-Rabin

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) 复杂度,和字串长度无关了。主要思路是每次计算只需要考虑原来头部和新增尾部的字符就可以了,中间部分不用重复循环计算。

Redis dict 的实现方法

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

Redis skiplist 的实现方法

  • redis 里面的有序集合应该就是使用 skiplist 和 dict 结合实现的。

  • skiplist 节点是有序的。

  • 每个节点可以有不同的层高,一般来说,层的数量多访问其他节点的速度就快。每个节点可以有一个或者多个前进指针,有一个后退指针。查找的时候可以先从高层查找,逐渐降低层数,这样比普通链表更快。

  • 插入新的节点的时候,层数是随机产生的,不会改变原来节点的层数。

Open Addressing, Cryptographic Hashing

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

  • 不使用链表

  • 遇到插入的时候遇到冲突,那么用一个新的 hash 函数再次 hash 看存那里,这样循环直到找到一个合适的位置。

  • 具体的探测可用地址的方法有简单的顺序线性探测,平方探测,伪随机探测等等,或者 double hashing。

  • 删除的时候,把被删除的位置放一个 delete 标记,而不是 None,否则查找的时候会出错。插入的时候对 delete 标记和 None 做相同处理即可,可以复用空间。

  • 线性探测会导致 clustering,导致存放数据不均衡。平方探测可能会导致不能探测到全部的空间。

  • 要保持负载因子不要太大,否则探测次数会变大。

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

大数的算术运算

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

广度优先搜索(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 遍历的反向输出可以排序,在完成一个节点的遍历之后,这个节点就是第一个需要完成的。

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 powered by Disqus