知识卡片

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

集合翻倍限制回指针改写

理解等级:高级

元素的回指针只在其所在短链被接到长链时改写。设某元素改写前所在集合大小为 s,长链大小至少也是 s,合并后它所在集合大小至少为 2s;从单元素集合开始,规模只能按 1、2、4、8……增长,达到 n 前最多改写 ⌊lg n⌋ 次。因此 n 个元素的全部回指针改写合计 O(n lg n),再加 m 次操作的常数开销,序列总成本为 O(m+n lg n)。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第19章 不相交集合的数据结构 · 查看原书依据

      Each time x’s pointer is updated, x must have started in the smaller set. The first time x’s pointer is updated, therefore, the resulting set must have at least 2 members. Similarly, the next time x’s pointer is updated, the resulting set must have had at least 4 members.

    参考来源

    - 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[10000,15000))。 - 结论依据:定理19.1按每个元素所属集合倍增证明回指针更新次数与总成本。 - 原始内容:Each time x ’s pointer is updated, x must have started in the smaller set. The first time x ’s pointer is updated, therefore, the resulting set must have at least 2 members. Similarly, the next time x ’s pointer is updated, the resulting set must have had at least 4 members.