知识卡片

普通读书笔记卡 · 3634

不相交集合支持合并与查找

理解等级:初级

不相交集合把n个元素始终划分为互不重叠的组。

UNION 合并两个组,FIND-SET 查询元素当前属于哪个组。以有根树配合按秩合并和路径压缩时,m 次操作的总时间为 O(mα(n));这里 α(n) 是逆 Ackermann 函数,随 n 增长极慢,但并非常数。

这个界对应整段操作序列的摊还总成本,并非每个单次操作都具有同样的最坏界。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第五部分 高级数据结构 · 查看原书依据

      Chapter 19 examines data structures for disjoint sets. Starting with a universe of n elements, each initially in its own singleton set, the operation UNION unites two sets. At all times, the n elements are partitioned into disjoint sets, even as calls to the UNION operation change the members of a set dynamically. The query FIND-SET identifies the unique set that contains a given element at the moment. Representing each set as a simple rooted tree yields surprisingly fast operations: a sequence of m operations runs in O(mα(n)) time

    参考来源

    - 位置:《算法导论(第4版)》第五部分引言《高级数据结构》(OEBPS/part005.xhtml,文本字符[0,5000))。 - 结论依据:原文分别定义UNION与FIND-SET,并给出有根树表示下m次操作的O(mα(n))总界。 - 原始内容:Chapter 19 examines data structures for disjoint sets. Starting with a universe of n elements, each initially in its own singleton set, the operation U NION unites two sets. At all times, the n elements are partitioned into disjoint sets, even as calls to the U NION operation change the members of a set dynamically. The query F IND -S ET identifies the unique set that contains a given element at the moment. Representing each set as a simple rooted tree yields surprisingly fast operations: a sequence of m operations runs in O ( mα ( n )) time