知识卡片

普通读书笔记卡 · 3634.a.6.c.2

并查集总界来自分项摊还

理解等级:高级

在同时采用按秩合并与路径压缩时,MAKE-SET 的摊还成本为 O(1),LINK 与 FIND-SET 各为 O(α(n));α(n) 是逆 Ackermann 函数,在实际规模上增长极慢。把 UNION 拆成两次查根加一次 LINK 后,每个原操作只产生常数次上述操作,所以 m 次原操作总成本为 O(mα(n))。

这是整个操作序列的摊还总界,并不保证每一次真实查找都只花 O(α(n));结论也依赖同时使用两种启发式。

这张卡片看不懂?

已有反馈 · 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. ▪