知识卡片
不相交集合支持合并与查找
不相交集合把n个元素始终划分为互不重叠的组。
UNION 合并两个组,FIND-SET 查询元素当前属于哪个组。以有根树配合按秩合并和路径压缩时,m 次操作的总时间为 O(mα(n));这里 α(n) 是逆 Ackermann 函数,随 n 增长极慢,但并非常数。
这个界对应整段操作序列的摊还总成本,并非每个单次操作都具有同样的最坏界。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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