并查集复杂度 并查集复杂度 目录
阿克曼函数
基础定义
union(x,y) 操作
find(a) 操作
为何并查集会被卡
关于启发式合并
本部分内容转载并修改自 时间复杂度 - 势能分析浅谈,已取得原作者授权同意.
这里,先给出 的定义.为了给出这个定义,先给出 的定义.
定义 为:
即阿克曼函数.
这里, 表示将 连续应用在 上 次,即 , .
再定义 为使得 的最小整数值.注意,我们之前将它描述为 ,反正他们的增长速度都很慢,值都不超过 4.
每个节点都有一个 rank.这里的 rank 不是节点个数,而是深度.节点的初始 rank 为 0,在合并的时候,如果两个节点的 rank 不同,则将 rank 小的节点