并查集复杂度
本部分内容转载并修改自 时间复杂度 - 势能分析浅谈,已取得原作者授权同意。
定义
阿克曼函数
这里,先给出
的定义。为了给出这个定义,先给出
的定义。
定义
为:
即阿克曼函数。
这里,
表示将
连续应用在
上
次,即
,
。
再定义
为使得
的最小整数值。注意,我们之前将它描述为
,反正他们的增长速度都很慢,值都不超过 4。
基础定义
每个节点都有一个 rank。这里的 rank 不是节点个数,而是深度。节点的初始 rank 为 0,在合并的时候,如果两个节点的 rank 不同,则将 rank 小的节点合并到 rank 大的节点上,并且不更新大节点的 rank 值。否则,随机将某个节点合并到另外一个节点上,将根节点的 rank 值 +1。这里根节点的 rank 给出了该树的高度。记 x 的 rank 为
,类似的,记 x 的父节点为
。我们总有
。
为了定义势函数,需要预先定义一个辅助函数
。其中,
。当
的时候,再定义一个辅助函数
。这些函数定义的
都满足
且
不是某个树的根。
上面那些定义可能让你有点头晕。再理一下,对于一个
和
,如果
,总是可以找到一对
令
,而
,在这个前提下,
。
描述了
的最大迭代级数,而
描述了在最大迭代级数时的最大迭代次数。
对于这两个函数,
总是随着操作的进行而增加或不变,如果
不增加,
也只会增加或不变。并且,它们总是满足以下两个不等式:
考虑
、
和
的定义,这些很容易被证明出来,就留给读者用于熟悉定义了。
定义势能函数
,其中
表示一整个并查集,而
为并查集中的一个节点。定义
为:
或为某棵树的根节点
然后就是通过操作引起的势能变化来证明摊还时间复杂度为
啦。注意,这里我们讨论的
操作保证了
和
都是某个树的根,因此不需要额外执行
和
。
可以发现,势能总是个非负数。另,在开始的时候,并查集的势能为
。
证明
union(x,y) 操作
其花费的时间为
,因此我们考虑其引起的势能的变化。
这里,我们假设
,即
被接到
上。这样,势能增加的节点仅有
(从树根变成非树根),
(秩可能增加)和操作前
的子节点(父节点的秩可能增加)。我们先证明操作前
的子节点
的势能不可能增加,并且如果减少了,至少减少
。
设操作前
的势能为
,操作后为
,这里
可以是任意一个
的非根节点,操作可以是任意操作,包括下面的 find 操作。我们分三种情况讨论。
和
并未增加。显然有
。
增加了,
并未增加。这里
至少增加一,即
,势能函数减少了,并且至少减少 1。
增加了,
可能减少。但是由于 $0
本页面最近更新:2025/5/24 12:24:08,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:orzAtalod, Enter-tainer, H-J-Granger, StudyingFather, CCXXXI, Friendseeker, iamtwz, NachtgeistW, R-fzx, Xeonacid, yusancky
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用