← 返回刚才阅读的位置

知识卡片

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

连接的势能增量有界

理解等级:高级

rank 是按秩合并维护的树高上界标签:不同秩的根连接时秩不变,同秩根连接时新根的秩加 1。α(n) 是逆 Ackermann 函数,也是本证明中每增加一单位根秩所允许增加的势能系数。

LINK 只接收两棵树的根,实际改一条父指针并可能把新根的 rank 加 1,所以实际成本为 O(1)。成为子节点的旧根势能不升;新根若因同秩合并把 rank 从 r 增至 r+1,其势能 α(n)·rank 至多增加 α(n)。因此森林总势能变化至多 α(n),摊还成本为 O(1)+α(n)=O(α(n))。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[30000,36000))。 - 结论依据:引理19.12分析父根秩变化,结论明确势能增加上界与摊还成本。 - 原始内容:The increase in potential due to the L INK operation, therefore, is at most α ( n ). The amortized cost of the L INK operation is O (1) + α ( n ) = O ( α ( n )). ▪