知识卡片
并查集总界来自分项摊还
在同时采用按秩合并与路径压缩时,MAKE-SET 的摊还成本为 O(1),LINK 与 FIND-SET 各为 O(α(n));α(n) 是逆 Ackermann 函数,在实际规模上增长极慢。把 UNION 拆成两次查根加一次 LINK 后,每个原操作只产生常数次上述操作,所以 m 次原操作总成本为 O(mα(n))。
这是整个操作序列的摊还总界,并不保证每一次真实查找都只花 O(α(n));结论也依赖同时使用两种启发式。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第19章 不相交集合的数据结构 · 查看原书依据
Theorem 19.14 A sequence of m MAKE-SET, UNION, and FIND-SET operations, n of which are MAKE-SET operations, can be performed on a disjoint-set forest with union by rank and path compression in O(m α(n)) time. Proof Immediate from Lemmas 19.7, 19.11, 19.12, and 19.13. ▪
参考来源
- 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[35000,40000))。
- 结论依据:定理19.14把前述引理的分项摊还界合并为整段序列上界。
- 原始内容:Theorem 19.14 A sequence of m M AKE -S ET , U NION , and F IND -S ET operations, n of which are M AKE -S ET operations, can be performed on a disjoint-set forest with union by rank and path compression in O ( m α ( n )) time. Proof Immediate from Lemmas 19.7, 19.11, 19.12, and 19.13. ▪