知识卡片
势能法汇总森林节点信用
并查集的摊还分析给每个节点 x 在第 q 次操作后的“信用”记作 φ_q(x),森林总势能为 Φ_q=∑_x φ_q(x)。初始还没有节点,所以 Φ₀=0;每个节点势能都非负。
一次操作的摊还成本等于实际成本加势能变化 ΔΦ。长 FIND-SET 虽访问很多节点,但路径压缩会降低沿途多数节点的势能;先前积累的信用因此可支付这次访问成本。势能是分析工具,不是实现中需要维护的字段。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第19章 不相交集合的数据结构 · 查看原书依据
The potential function we use assigns a potential ϕq(x) to each node x in the disjoint-set forest after q operations. For the potential Φq of the entire forest after q operations, sum the individual node potentials: . Because the forest is empty before the first operation, the sum is taken over an empty set, and so Φ0 = 0. No potential Φq is ever negative.
参考来源
- 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[25000,30000))。
- 结论依据:原文定义逐节点势能、森林总势能、初始零值和非负条件。
- 原始内容:The potential function we use assigns a potential ϕ q ( x ) to each node x in the disjoint-set forest after q operations. For the potential Φ q of the entire forest after q operations, sum the individual node potentials: . Because the forest is empty before the first operation, the sum is taken over an empty set, and so Φ 0 = 0. No potential Φ q is ever negative.