知识卡片
连接的势能增量有界
rank 是按秩合并维护的树高上界标签:不同秩的根连接时秩不变,同秩根连接时新根的秩加 1。α(n) 是逆 Ackermann 函数,也是本证明中每增加一单位根秩所允许增加的势能系数。
LINK 只接收两棵树的根,实际改一条父指针并可能把新根的 rank 加 1,所以实际成本为 O(1)。成为子节点的旧根势能不升;新根若因同秩合并把 rank 从 r 增至 r+1,其势能 α(n)·rank 至多增加 α(n)。因此森林总势能变化至多 α(n),摊还成本为 O(1)+α(n)=O(α(n))。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第19章 不相交集合的数据结构 · 查看原书依据
The increase in potential due to the LINK operation, therefore, is at most α(n). The amortized cost of the LINK operation is O(1) + α(n) = O(α(n)). ▪
参考来源
- 位置:《算法导论(第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 )). ▪