知识卡片
朴素链表合并可能平方
若总把第二条链表接到第一条末尾,需要逐个改写第二条链表元素的所属集合指针。最坏顺序是每次把当前长链作为第二条链:依次合并规模 1 与 1、1 与 2、1 与 3……时,被改写节点数为 1+2+⋯+(n−1)=n(n−1)/2=Θ(n²)。因此常数时间的 FIND-SET 是把代价转移给 UNION,并未让整个操作序列变成线性时间。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第19章 不相交集合的数据结构 · 查看原书依据
The UNION operation is where this implementation pays the price for FIND-SET taking constant time: UNION must also update the pointer to the set object for each object originally on y’s list, which takes time linear in the length of y’s list.
参考来源
- 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[5000,10000))。
- 结论依据:原文解释合并需要改写整条被接入链表的回指针,并构造平方序列。
- 原始内容:The U NION operation is where this implementation pays the price for F IND -S ET taking constant time: U NION must also update the pointer to the set object for each object originally on y ’s list, which takes time linear in the length of y ’s list.