算法
参考资料
基础
- 讲了一下 Java 与面向对象
- 讲了一下线性表, 数组, 链表, 栈, 队列
- 斯特林公式 - 用于估计阶乘的近似值
- \(n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n\)
- \(lg(n)! \approx nlg(n) - n + \frac{1}{2}lg(2\pi n)\)
- 为了解决对输入的依赖
- 针对可能的最坏情况 -> 引入随机化 (快速排序)
- 针对可能的高代价操作情况 -> 考虑代价均摊 (vector 倍增大小)
排序
简单排序
- 选择排序 \(O(n)\) 的交换次数
- 插入排序找插入位置时顺手移位, 很快
- 希尔排序在大尺度下相对有序数组上显然快
- 即使无该特征, 希尔排序也乐于制造该特征去优化接下来的子插入排序
- 这使其时间负杂度稳定性极强
归并排序
快速排序
- 注意原地切分 + 边界条件 + 与切分相等时的处理
- 改进
- 小数组时, 切换到插入排序
- 三取样切分, 取子数组的首中尾三个元素, 取其中位数作为切分元素
- 将切分值放在数组末尾, 作为哨兵, 避免对越界的判断
- 对于有大量重复元素的数组
- Dijkstra 想出三向切分, 切分元素为 v, 数组被切分为三部分, 小于 v, 等于 v, 大于 v
- 但他的实现有点问题, 对于普通情况, 交换次数会多一些, 然后就被优化为将等于 v 的元素都交换到数组两侧, 最后归位
- 三向切分在重复元素较多时, 可以将排序时间从 \(O(nlg(n))\) 减少到 \(O(n)\) (通过对输入的信息预设突破了理论下限)
- 将输入的主键频率量化为信息熵, 可以求得该优化的理论时间复杂度
优先队列
- 用多叉堆平衡高度与常数
- 堆排序缓存命中率低
- 堆排序常用先沉后浮
- 一方面下沉优于上浮
- 另一方面下沉时, 隐式将较大的子节点上浮
查询
符号表
二叉查找树
平衡查找树
- 2-3 查找树, 有一点容错, 表现优秀一点
- 红黑树, 换个方式的容错, 表现更好, 除
put 外不引入复杂机制
散列表
图
无向图
- Floyd-Warshall 算法, 可用于求图可达性
有向图
- 求有向图的强连通分量
- Kosaraju 算法
- 深度优先搜索查找给定有向图的所有顶点
- 根据由此得到的所有顶点的逆序, 再次用深度优先搜索处理有向图的转置图
- 每次深度优先搜索遍历到的所有顶点, 就是一个强连通分量
- Tarjan 算法
- 深度优先搜索遍历图
- 维护一个栈, 记录遍历的顶点
- 对于每个顶点, 记录其发现时间, 可到达的最小发现时间
- 当发现一个未访问的顶点时, 递归访问它的邻接, 更新低链接值
- 当回溯到一个顶点时, 如果该顶点的低链接值等于发现时间, 则弹出栈中所有的顶点, 该顶点就是一个强连通分量的根
- 先求强连通分量, 将每个强连通分量看作一个顶点, 再用 Floyd-Warshall 算法求可达性
最小生成树
- 在一幅加权图中, 给定任意的切分, 它的横切边中的权重最小者必然属于图的最小生成树
- 经典算法无法应用于有向图, 那是另一个叫最小树形图的问题
- 针对 \(V\) 个顶点 \(E\) 条边, 最坏情况下的增长数量级:
| 算 法 |
空 间 |
时 间 |
| 延时的 Prim 算法 |
\(O(E)\) |
\(O(ElogE)\) |
| 即时的 Prim 算法 |
\(O(V)\) |
\(O(ElogV)\) |
| Kruskal |
\(O(E)\) |
\(O(ElogE)\) |
| Fredman-Tarjan |
\(O(V)\) |
\(O(E+VlogV)\) |
| Chazelle |
\(O(V)\) |
非常接近但还没有达到 \(O(E)\) |
| 理想情况 |
\(O(V)\) |
\(O(E)\)? |
延时的 Prim 算法
- 从任意节点开始
- 扫描该节点的所有邻接边加入优先队列
- 循环弹出权重最小的边 \((u, v)\)
- 如果 \(u\) 和 \(v\) 都已经被标记为 visited 说明这条边失效了
- 如果 \(v\) 没访问过则将 \(v\) 加入 MST, 标记 \(v\) 为 visited, 并将 \(v\) 的所有邻接边加入优先队列
即时的 Prim 算法
- 对延时 Prim 算法必须遍历边的改进
- 与其在队列里存边, 不如存节点, 我们只关心从当前生成树到某个非树节点 \(v\) 的最短距离
- 一个索引优先队列不仅能排序, 还支持
decrease-key 操作, 维护当前到某点的最小权重
- PQ 中存储节点索引, Key 是当前到该节点的最小权重
- 循环弹出 PQ 中权重最小的节点 \(v\)
- 松弛操作遍历 \(v\) 的邻居 \(w\)
- 如果 \(w\) 不在 MST 中, 且边 \((v, w)\) 的权重 <
distTo[w], 则更新 distTo[w], 并更新 PQ 中 \(w\) 的优先级 (decrease-key)
Kruskal 算法
- 永远先选全图中权重最小的边, 只要这条边不和已选的边构成环, 就要它
- 将所有 \(E\) 条边按权重从小到大排序
- 遍历排序后的边 \((u, v)\), 用并查集查询 \(u\) 和 \(v\) 是否在同一个集合
- 如果是跳过
- 如果否将这条边加入 MST, 并将 \(u\) 和 \(v\) 所在的集合合并
Fredman-Tarjan 算法
- 其实就是 Eager Prim 算法的加强版, 用上了斐波那契堆
- 斐波那契堆
decrease-key 操作的摊还时间复杂度是 \(O(1)\), 而不是 \(\log V\)
- 但是
extract-min仍然是 \(O(\log V)\)
其他
- Chazelle 算法使用了 Soft Heap 数据结构
- 软堆允许在返回值上犯错, 即它可能会人为地提高某些键的值
- Chazelle 设计了一个非常精妙的算法, 即使堆里的数据是不完全准确的, 也能通过特定的修补逻辑保证最终找出的 MST 是完全正确的
- 时间 \(O(E \cdot \alpha(E, V))\), \(\alpha\) 是阿克曼函数的反函数, 这个函数增长极慢, 对于宇宙中所有实际规模的数据, \(\alpha < 5\)
- 随机化算法
- 其期望时间复杂度确实是 \(O(V+E)\), 通过随机采样部分边来剔除那些肯定不在 MST 中的重边, 从而达到线性速度
- 目前最接近的确定性算法是 Pettie 和 Ramachandran 提出的基于最优决策树的算法
- 它的复杂度被证明是最优的, 但这个最优的具体表达式极其复杂, 目前尚无法证明它是否严格等于 \(O(E)\)
最短路径
- 边的松弛操作
- 对于边 \((u, v)\) 权重为 \(w\), 如果 \(distTo[v] > distTo[u] + w\), 则更新 \(distTo[v] = distTo[u] + w\)
- 就是尝试用改变修正最短路
- 点的松弛操作
- 最短路径的通用算法为对所有边对进行松弛操作 (不计顺序)
Dijkstra 算法
- 从源点开始, 对所有邻接点进行松弛操作 (这个顺序保证只松弛附近的)
- 无法解决负权重边的问题
- 算法太开放, 优化方案很多, 针对不同特点图有不同的优化
无环图的优化
- 按拓扑排序进行松弛操作 (这个顺序保证只松弛接下来的)
Bellman-Ford 算法
- 对所有边进行 \(n-1\) 次松弛操作 (即使不邻接)
- 可以解决负权重边的问题, 但不能解决负权重环
- 常用其优化, SPFA 算法 (只遍历触发更新的节点的出边, 放队列里)
字符串
字符串排序
键索引计数法
低位优先的字符串排序 / 高位优先的字符串排序
三向字符串快速排序
单词查找树
- 三向单词查找树, 每个节点有三个指针, 分别指向小于, 等于, 大于该字符的子树 (避免 26 叉)
子字符串查找
Rabin-Karp 算法
- 将模式串哈希, 对文本中每个长度为 \(m\) 的子串哈希, 与模式串哈希比较
- 问题转为为了线性的滑动窗口哈希
- 哈希函数 \(h(s) = s[0] * R^{m-1} + s[1] * R^{m-2} + \cdots + s[m-1] * R^0\)
- \(R\) 是一个素数, 比如 \(31\)
- 对哈希值取模, 防止溢出
- 最后需要比较是否相等, 因为哈希冲突是可能的
- 蒙特卡洛算法为概率对比, 不保证正确性, 但期望时间复杂度为 \(O(n)\)
- 将哈希值取余的 \(Q\) 设为大于 \(10^20\) 的素数
正则表达式
- 连接操作, 比如
ab 匹配 a 后面跟着 b
- 或操作, 比如
a|b 匹配 a 或 b
- 闭包操作, 比如
a* 匹配 a 重复 0 次或多次
- 以下为简化操作
. 匹配任意字符[abc] 匹配 a, b, c 中的任意一个[^abc] 匹配除了 a, b, c 以外的任意字符[a-z] 匹配 a 到 z 中的任意字符+ 匹配 1 次或多次? 匹配 0 次或 1 次{n} 匹配 n 次{n,} 匹配 n 次或多次{n,m} 匹配 n 到 m 次
\\ 转义字符, 比如 \\. 匹配 ., \\[ 匹配 [- Kleene 定理, 任何正则表达式都可以转换为等价的 NFA (非确定性有限状态自动机)
数据压缩
- 任何数据压缩算法的效果都十分依赖于输入的特征
- 不存在能够压缩任意比特流的算法
双位编码压缩
- 如果字符集没占满一个字节, 可以用一个字节的高低部分表示字符
游程编码
霍夫曼压缩
LZW 压缩算法
- 解压时不需要发送压缩字典
- 建立一个字典, 把遇到的重复字符串映射为很短的代码
- 一边读取数据, 一边寻找还没见过的字符组合, 一旦遇到一个新的组合, 就给它分配一个新的编号, 并放入字典, 下次再遇到就用编号代替
- 特殊情况, 字典里没有 \(NEW\), 这通常发生在编码器刚生成一个新词紧接着立马就用它的情况
- 这时候输出上一个代码的串 + 该串的首字符
- 将这个内容添加到字典
背景
B树
- 我们使用页的访问次数作为外部查找算法的成本模型
- 一类变化是尽可能在内部结点中保存更多的页引用以节省时间 (B+ 树)
- 另一类变化是在分裂前将兄弟结点合并以提高存储的使用效率
后缀数组
- 将字符串的所有后缀排序, 就得到了后缀数组
- 快速获得最长重复子字符串
- 有线性时间获得后缀数组的算法
网络流算法
- 一个流量网络是一张边的权重 (这里称为容量) 为正的加权有向图
- 一个 s/t 流量网络有两个已知的顶点, 即起点 \(S\) 和终点 \(t\)
- 如果所有边的流量均小于边的容量且满足每个顶点的局部平衡, 则称这种流量配置方案是可行的
增广路径算法 (Ford-Fulkerson 算法)
- 增广路径是指从 \(S\) 到 \(t\) 的一条路径, 满足路径上的所有边的残量 (容量 - 流量) 均大于 0
- 网络中的初始流量为零, 沿着任意从起点到终点 (且不含有饱和的正向边或是空逆向边) 的增广路径增大流量, 直到网络中不存在这样的路径为止
- 无论我们如何选择路径, 该方法总能找出最大流量
最大流 - 最小切分定理
- s/t 切分是一个将顶点 \(S\) 和顶点 \(t\) 分配于不同集合中的切分
- 对于任意流量网络, 每种 s/t 切分中的跨切分流量都和总流量的值相等
- 最大流等于最小切割边的总容量
剩余流量网络
- 剩余流量网络 \(G_f\) 指示了在当前流量配置下网络中剩余的可用容量
- 对于原图中的每条边 \((u, v)\), 如果其流量小于容量, 则在 \(G_f\) 中包含一条容量为 \(c_{uv} - f_{uv}\) 的前向边
- 对于原图中的每条边 \((u, v)\), 如果其流量大于 0, 则在 \(G_f\) 中包含一条容量为 \(f_{uv}\) 的后向边 (允许撤销流量)
- 剩余流量网络中从 \(S\) 到 \(t\) 的任意路径均对应原网络中的一条增广路径
最短增广路径算法 (Edmonds-Karp 算法)
- 这是 Ford-Fulkerson 算法的一种特定实现, 区别在于选择增广路径的策略
- 在每一步中, 总是选择剩余流量网络中边数最少 (即无权最短路径) 的增广路径来增加流量
- 该算法通过广度优先搜索 (BFS) 来寻找路径, 保证了增广路径的长度在迭代过程中单调不减
规约
- 我们常证明一个基本算法的正确性, 然后通过规约证明其他算法的正确性
不可解性
- 图灵机可以模拟所有物理可实现的计算设备 (未被证明)
- 图灵机无法解决的问题是存在的
- 在任意计算设备上解决某个问题的某个程序所需的运行时间的增长数量级都是在图灵机上解决该问题的某个程序的多项式倍数 (未被证明)
- 如果一个问题有解且验证它的解的正确性所需的时间不会超过输入规模的多项式, 则称这种问题为搜索问题, 当一个算法给出了一个解或是已证明解不存在时, 就称它解决了一个搜索问题
- 后续略, 来日方长