知识卡片

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

长查找路径由势能下降支付

理解等级:高级

rank 是按秩合并维护的树高上界标签,α(n) 是逆 Ackermann 函数;level 记录父秩达到的 Ackermann 粗层,iter 记录该层内越过阈值的次数。路径压缩把节点直接接向高秩根,会让多数节点的 level 或 iter 前进,从而降低势能。

设 FIND-SET 的查找路径有 s 个节点,实际成本为 O(s)。按 level 分组后,每层至多留下最后一个节点不保证降势能,另有秩为 0 的首节点和根节点两个例外;level 只有 0 到 α(n)−1,所以例外最多 α(n)+2 个。

其余至少 max(0,s−α(n)−2) 个节点在压缩后各降至少一单位势能。严格做常数核算时,可把整套节点势能乘以足以覆盖“访问一个节点”常数成本的固定系数;这样每个普通节点释放的信用抵消其访问成本,只留下至多 α(n)+2 个例外节点。因此摊还成本为 O(α(n));这不是声称单次真实查找只访问 α(n) 个节点。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[35000,40000))。 - 结论依据:引理19.13给出最多 α(n)+2 个例外节点及其余节点势能下降的计数;势能乘固定常数是将该单位下降与 O(s) 实际成本的隐藏常数对齐,不改变渐近界。 - 原始内容:We will show that no node’s potential increases due to the F IND -S ET and that at least max {0, s − ( α ( n ) + 2)} nodes on the find path have their potential decrease by at least 1.