知识卡片
两种启发式得到近线性界
按秩合并让矮树挂到高树,路径压缩则让一次 FIND-SET 路径上的节点直接指向根。两者一起使用时,n 次建集包含在 m 次操作中,整个序列的最坏成本为 O(mα(n));α(n) 是快速增长函数族的反函数,在任何实际可表示的 n 上都不超过 4。于是每次操作的摊还成本实践中近似常数,但 α 仍会随 n 增长,数学上不能把结论改写成严格的 O(m)。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第19章 不相交集合的数据结构 · 查看原书依据
Combining union by rank and path compression gives a worst-case running time of O(m α(n)), where α(n) is a very slowly growing function, defined in Section 19.4. In any conceivable application of a disjoint-set data structure, α(n) ≤ 4, and thus, its running time is as good as linear in m for all practical purposes. Mathematically speaking, however, it is superlinear.
参考来源
- 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[20000,25000))。
- 结论依据:原文给出组合启发式的O(mα(n))界并明确其实际与数学上的区别。
- 原始内容:Combining union by rank and path compression gives a worst-case running time of O ( m α ( n )), where α ( n ) is a very slowly growing function, defined in Section 19.4 . In any conceivable application of a disjoint-set data structure, α ( n ) ≤ 4, and thus, its running time is as good as linear in m for all practical purposes. Mathematically speaking, however, it is superlinear.