← 返回刚才阅读的位置

知识卡片

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

节点势能有非负上界

理解等级:高级

rank 是按秩合并维护的树高上界标签,α(n) 是增长极快的 Ackermann 层级的反函数。对非根节点,level(x) 表示父节点秩相对 x.rank 已跨到哪个 Ackermann 层,iter(x) 表示在该层阈值中又推进了多少次。

节点 x 的势能按两种情况定义:若 x 是根或 rank=0,则 φ(x)=α(n)·rank;否则 φ(x)=(α(n)−level(x))·rank−iter(x)。其中 0≤level(x)<α(n),且正秩节点满足 1≤iter(x)≤rank。

代入极端值可得 0≤φ(x)≤α(n)·rank:非负保证分析不会靠“负信用”支付无限成本,上界则把可积累信用限制在秩的倍数内。这些量只服务于摊还证明。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[30000,35000))。 - 结论依据:式(19.7)给出分段势能,式(19.4)、(19.6)分别限制 level 与 iter;引理19.8把这些界代入势能式,推出 0≤φ_q(x)≤α(n)·x.rank。 - 原始内容:Lemma 19.8 For every node x , and for all operation counts q , we have 0 ≤ ϕ q ( x ) ≤ α ( n ) · x . rank .