2020-2021:teams:no_morning_training:shaco:知识点:数据结构:并查集
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:no_morning_training:shaco:知识点:数据结构:并查集 [2020/07/02 11:22] shaco |
2020-2021:teams:no_morning_training:shaco:知识点:数据结构:并查集 [2020/07/06 09:15] (当前版本) shaco |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| 并查集应用广泛，用于判断元素是否属于同一个集合以及合并集合。 | 并查集应用广泛，用于判断元素是否属于同一个集合以及合并集合。 | ||
| ==== 复杂度 ==== | ==== 复杂度 ==== | ||
| - | 最坏到 $O(n)$，单独使用路径压缩达到 $O(n+f(1+\log_{2+f/n}n))$，单独使用按秩合并可达到 $O(\log{n})$，两者同时使用可以达到 $O(\alpha (n))$，其中 $\alpha (n)$ 是阿克曼函数的反函数，可以认为非常小（这部分参照网上）。按秩合并即每次将小的集合合并到大的集合中去，可以减少修改次数。 | + | 最坏到 $O(n)$，单独使用路径压缩达到 $O(n+f(1+\log_{2+f/n}n))$，单独使用按秩合并可达到 $O(\log{n})$，两者同时使用可以达到 $O(\alpha (n))$，其中 $\alpha (n)$ 是阿克曼函数的反函数，可以认为非常小。按秩合并即每次将小的集合合并到大的集合中去，可以减少修改次数。 |
| ==== 概念 ==== | ==== 概念 ==== | ||
| 每个集合有一个代表元素，每一个元素通过一个数组记录其所属集合的代表元素。判断两个元素是否属于同一个集合时查询它们的代表元素是否相同，合并集合时将一个集合的代表元素更替为另一个集合的代表元素。 | 每个集合有一个代表元素，每一个元素通过一个数组记录其所属集合的代表元素。判断两个元素是否属于同一个集合时查询它们的代表元素是否相同，合并集合时将一个集合的代表元素更替为另一个集合的代表元素。 | ||
2020-2021/teams/no_morning_training/shaco/知识点/数据结构/并查集.1593660147.txt.gz · 最后更改: 2020/07/02 11:22 由 shaco
