MENU

Category: 算法

拓扑排序

一:前言

在有向无环图(DAG,即 Directed Acyclic Graph)中,拓扑排序(Topological Sorting)是其顶点的线性排序,使得对于从顶点 $u$ 到顶点 $v$ 的每个有向边,在排序中 $u$ 都在 $v$ 之前。

Read More

树状数组

一:前言

树状数组,也叫二叉索引树(Binary Indexed Tree,简称 BIT),由 Peter M. Fenwick 于 1994 年发表。其初衷是解决数据压缩里累积频率(Cumulative Frequency)的计算问题,现多用于动态地计算数组的区间和。

Read More

并查集

一:背景

并查集(Union-Find Set),也叫Disjoint Set,由Bernard A. Galler和Michael J. Fischer在1964年提出,它主要是用来解决动态连通性问题。

Read More

Rabin–Karp算法

一:背景

Rabin-Karp算法(也可以叫Karp-Rabin算法),由Richard M. Karp和Michael O. Rabin在1987年发表,它也是用来解决多模式串匹配问题的。

Read More