知识卡片
压缩分析的层级只会升高
rank 是按秩合并维护的树高上界标签,A_k 是 Ackermann 型快速增长函数族的第 k 层。对正秩非根节点 x,分析量 level(x) 定义为满足 A_k(x.rank)≤x.p.rank 的最大层 k;x.p 表示父节点。它衡量“父节点秩相对 x 的秩跨过了快速增长函数的哪一层”,并非树的真实深度。
x 一旦不再是根,其 rank 固定;父节点的 rank 随后只会不变或增大。于是上述不等式能成立的最大 k 只会增大,level(x) 随时间单调不减。另一个分析量 iter(x) 记录在当前 level 内还能反复应用多少次 A_level;level 不变时,iter 也只会不变或增大。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第19章 不相交集合的数据结构 · 查看原书依据
For a given nonroot node x, the value of level(x) monotonically increases over time. Why? Because x is not a root, its rank does not change. The rank of x.p monotonically increases over time, since if x.p is not a root then its rank does not change, and if x.p is a root then its rank can never decrease.
参考来源
- 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[25000,30000))。
- 结论依据:原文式(19.3)把 level(x) 定义为满足 A_k(x.rank)≤x.p.rank 的最大 k,式(19.5)定义 iter(x);随后以子节点秩固定、父节点秩不降推出 level 单调,并说明 level 不变时 iter 不降。
- 原始内容:For a given nonroot node x , the value of level( x ) monotonically increases over time. Why? Because x is not a root, its rank does not change. The rank of x . p monotonically increases over time, since if x . p is not a root then its rank does not change, and if x . p is a root then its rank can never decrease.