skewheap_amortized analysis(王灿)1
需积分: 0 167 浏览量
2022-08-03
16:57:39
上传
评论
收藏 1.29MB PDF 举报
1 势能分析方法回顾 1
大家请对照课程 PPT 的第 11 页和 12 页阅读下面材料。
1 势能分析方法回顾
首先回顾下均摊分析的势能方法：
D
i
：执行第 i 步操作后的数据结构；
D
0
：初始数据结构；
势能函数：Φ : D
i
→ R，反应操作后数据结构的势能；
c
i
: 将 D
i
− 1 变换到 D
i
的实际成本；
ˆc
i
: 将 D
i
− 1 变换到 D
i
的均摊成本，我们有： ˆc
i
= c
i
+ Φ(D
i
) − Φ(D
i−1
)；所以，总均摊成本为：
n
i=1
ˆc
i
=
n
i=1
c
i
+ Φ(D
n
) − Φ(D
0
)
在这个总均摊成本的计算中，如果我们能够保证 Φ(D
n
) − Φ(D
0
) ≥ 0，我们就能保证总均摊成本是总
实际成本的一个上限。势能方法的关键是找到合适的势能函数。一般一个好的势能函数设计总能使 Φ(D
0
)
是这个序列中的最小值。实际使用中，我们一般定义 Φ(D
0
) = 0。这样，只要证明上式中 Φ(D
i
) ≥ 0，就
可以证明均摊成本是实际成本的一个上限。
2 斜堆合并的均摊分析
斜堆合并的总步骤数就是两个堆的右路径节点数之和；但是斜堆右路径长度不受限，最坏情况可到
O(n)，所以我们需要通过均摊分析来确定 M 个操作序列的复杂度。
均摊分析的势能函数要反映斜堆合并操作的效果。考虑到合并成本为右路径总节点数，直接想法是通
过右路径节点数目来定义势能函数（斜堆合并由空堆开始，因此该函数刚好从 0 开始且非负）。但该函数
的问题是单调递增的，不能反映合并过程中的势能变化。
我们选择斜堆中的“重节点（heavy nodes）”数作为势能函数。如果一个节点的右子树总结点数占该
节点为根的子树总结点数达一半及以上为重节点，反之为轻节点。注意到斜堆合并是由空堆开始，该势能
函数满足：Φ(D
0
) = 0；随着合并的进展，中间任何步骤都有 Φ(D
0
) ≥ 0。
假设要合并的两斜堆 H
1
和 H
2
右路径上的重节点数分别为 h
1
和 h
2
。俩斜堆中其他重节点数目为 h。
则有：
Φ(D
0
) = h
1
+ h
2
+ h
注意在合并过程中，除了右路径节点，其他节点不会发生轻重转变，因为它们的左右子树都没有变化。
因为合并成本为右路径总节点数，如果 H
1
和 H
2
右路径上的轻节点数分别为 l
1
和 l
2
，则实际合并的
总代价为：
n
i=1
c
i
= l
1
+ l
2
+ h
1
+ h
2
合并后，只有右路径节点会出现轻重节点的改变：（1）右路径重节点合并后会肯定变成轻节点（左右
调换后，左轻右重自然变成了左重右轻）；（2）右路径轻节点合并后有可能变成重节点。所以合并后重
节点数目最多的情况就是所有右路径的轻节点都变重节点的情况。所以：Φ(D
N
) ≤ l
1
+ l
2
+ h。所以：
(Φ(D
N
) − Φ(D
0
)) ≤ l
1
+ l
2
− h
1
− h
2
。所以：
n
i=1
ˆc
i
=
n
i=1
c
i
+ (Φ(D
N
) − Φ(D
0
)) ≤ 2(l
1
+ l
2
)
l
1
和 l
2
为要合并的俩斜堆右路径上轻节点数量。轻节点意味着节点的子树“左重右轻”（和前面讲过的左
倾堆类似），因此 l
1
+ l
2
≤ log N
1
+ log N
2
（N
1
和 N
2
分别为俩斜堆的节点数）。
罗小熙
- 粉丝: 16
- 资源: 319
最新资源
- MyBatis动态SQL是一种强大的特性，它允许我们在SQL语句中根据条件动态地添加或删除某些部分，从而实现更加灵活和高效的数据
- MyBatis动态SQL是一种强大的特性，它允许我们在SQL语句中根据条件动态地添加或删除某些部分，从而实现更加灵活和高效的数据
- 【ERP标准流程-标准流程-进货管理】（DOC 17页）.doc
- MyBatis动态SQL是一种强大的特性，它允许我们在SQL语句中根据条件动态地添加或删除某些部分，从而实现更加灵活和高效的数据
- MyBatis动态SQL是一种强大的特性，它允许我们在SQL语句中根据条件动态地添加或删除某些部分，从而实现更加灵活和高效的数据
- Java爬虫项目【项目开发计划】（共12页）.docx
- 11111111111
- MyBatis动态SQL是一种强大的特性，它允许我们在SQL语句中根据条件动态地添加或删除某些部分，从而实现更加灵活和高效的数据
- MyBatis动态SQL是一种强大的特性，它允许我们在SQL语句中根据条件动态地添加或删除某些部分，从而实现更加灵活和高效的数据
- MyBatis动态SQL是一种强大的特性，它允许我们在SQL语句中根据条件动态地添加或删除某些部分，从而实现更加灵活和高效的数据
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0