知识卡片
并集分析可拆为查根与连接
UNION(x,y) 可分解为两次 FIND-SET 查出各自树根,再调用一次只接收树根的 LINK。每次原操作最多变成三次,序列长度只差常数倍,因此可先分析 LINK 版序列,再把界转回原操作。
若 LINK 版的每次操作摊还为 O(α(n)),其中 α 是增长极慢的逆 Ackermann 函数,原序列总成本仍为 O(mα(n));拆分只改变常数因子,不改变渐近阶。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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.