知识卡片

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

势能法汇总森林节点信用

理解等级:高级

并查集的摊还分析给每个节点 x 在第 q 次操作后的“信用”记作 φ_q(x),森林总势能为 Φ_q=∑_x φ_q(x)。初始还没有节点,所以 Φ₀=0;每个节点势能都非负。

一次操作的摊还成本等于实际成本加势能变化 ΔΦ。长 FIND-SET 虽访问很多节点,但路径压缩会降低沿途多数节点的势能;先前积累的信用因此可支付这次访问成本。势能是分析工具,不是实现中需要维护的字段。

这张卡片看不懂?

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