知识卡片

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

朴素链表合并可能平方

理解等级:高级

若总把第二条链表接到第一条末尾,需要逐个改写第二条链表元素的所属集合指针。最坏顺序是每次把当前长链作为第二条链:依次合并规模 1 与 1、1 与 2、1 与 3……时,被改写节点数为 1+2+⋯+(n−1)=n(n−1)/2=Θ(n²)。因此常数时间的 FIND-SET 是把代价转移给 UNION,并未让整个操作序列变成线性时间。

这张卡片看不懂?

已有反馈 · 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.