知识卡片
集合翻倍限制回指针改写
元素的回指针只在其所在短链被接到长链时改写。设某元素改写前所在集合大小为 s,长链大小至少也是 s,合并后它所在集合大小至少为 2s;从单元素集合开始,规模只能按 1、2、4、8……增长,达到 n 前最多改写 ⌊lg n⌋ 次。因此 n 个元素的全部回指针改写合计 O(n lg n),再加 m 次操作的常数开销,序列总成本为 O(m+n lg n)。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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.