知识卡片

普通读书笔记卡 · 3634.a.6.c

两种启发式得到近线性界

理解等级:高级

按秩合并让矮树挂到高树,路径压缩则让一次 FIND-SET 路径上的节点直接指向根。两者一起使用时,n 次建集包含在 m 次操作中,整个序列的最坏成本为 O(mα(n));α(n) 是快速增长函数族的反函数,在任何实际可表示的 n 上都不超过 4。于是每次操作的摊还成本实践中近似常数,但 α 仍会随 n 增长,数学上不能把结论改写成严格的 O(m)。

这张卡片看不懂?

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