知识卡片

普通读书笔记卡 · 3634.a.3.a

并集分析可拆为查根与连接

理解等级:高级

UNION(x,y) 可分解为两次 FIND-SET 查出各自树根,再调用一次只接收树根的 LINK。每次原操作最多变成三次,序列长度只差常数倍,因此可先分析 LINK 版序列,再把界转回原操作。

若 LINK 版的每次操作摊还为 O(α(n)),其中 α 是增长极慢的逆 Ackermann 函数,原序列总成本仍为 O(mα(n));拆分只改变常数因子,不改变渐近阶。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第19章 不相交集合的数据结构 · 查看原书依据

      Lemma 19.7 Suppose that we convert a sequence S′ of m′ MAKE-SET, UNION, and FIND-SET operations into a sequence S of m MAKE-SET, LINK, and FIND-SET operations by turning each UNION into two FIND-SET operations followed by one LINK. Then, if sequence S runs in O(mα(n)) time, sequence S′ runs in O(m′ α(n)) time.

    参考来源

    - 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[25000,30000))。 - 结论依据:引理19.7用操作替换和序列长度的常数倍关系证明复杂度可转移。 - 原始内容:Lemma 19.7 Suppose that we convert a sequence S ′ of m ′ M AKE -S ET , U NION , and F IND -S ET operations into a sequence S of m M AKE -S ET , L INK , and F IND -S ET operations by turning each U NION into two F IND -S ET operations followed by one L INK . Then, if sequence S runs in O ( mα ( n )) time, sequence S ′ runs in O ( m ′ α ( n )) time.