知识卡片
长查找路径由势能下降支付
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) 个节点。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第19章 不相交集合的数据结构 · 查看原书依据
We will show that no node’s potential increases due to the FIND-SET and that at least max {0, s − (α(n) + 2)} nodes on the find path have their potential decrease by at least 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.