知识卡片

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

路径压缩可消耗势能

理解等级:高级

rank 是按秩合并维护的树高上界标签,α 是逆 Ackermann 函数。对非根节点,level 记录父秩跨过的粗粒度 Ackermann 层,iter 记录当前层内继续跨过的阈值次数;父指针改接到更高秩祖先时,这两个量只会向前推进。

对非根节点,LINK 或 FIND-SET 不会提高其势能。若正秩节点的 level 增加 1,势能式中的 (α−level)·rank 至少减少 rank;即使 iter 随换层最多回落 rank−1,净势能仍至少下降 1。若 level 不变而 iter 增加,势能中的 −iter 也至少再减 1。

路径压缩把沿途节点改接到高秩根,正是推动这些分析量变化的动作。因此一次长查找访问的多数节点,会各释放至少一单位势能来抵消实际成本。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第19章 不相交集合的数据结构 · 查看原书依据

      Lemma 19.10 Let x be a node that is not a root, and suppose that the qth operation is either a LINK or a FIND-SET. Then after the qth operation, ϕq(x) ≤ ϕq−1(x). Moreover, if x.rank ≥ 1 and either level(x) or iter(x) changes due to the qth operation, then ϕq(x) ≤ ϕq−1(x) − 1.

    参考来源

    - 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[30000,35000))。 - 结论依据:引理19.10按“level 不变、iter 增加”和“level 增加、iter 可能回落”两种情况代入式(19.7),证明非根节点势能不增,且任一辅助量变化时净下降至少 1。 - 原始内容:Lemma 19.10 Let x be a node that is not a root, and suppose that the q th operation is either a L INK or a F IND -S ET . Then after the q th operation, ϕ q ( x ) ≤ ϕ q −1 ( x ). Moreover, if x . rank ≥ 1 and either level( x ) or iter( x ) changes due to the q th operation, then ϕ q ( x ) ≤ ϕ q −1 ( x ) − 1.