作者firejox (Tangent)
看板Prob_Solve
标题[心得] Leonardo Heap的 amortized analysis
时间Wed May 15 00:12:50 2019
因为对smooth sort所用到的资料结构有点兴趣，所以就拿来练习分析了，
有错欢迎鞭。
首先定义 L-tree 与 Leonardo Heap
L-tree 是一个二元树并满足以下性质：
1. order为 0 跟 1 的 L-tree 皆为一个节点
2. order为 m 的 L-tree 的左子树为 order m-1 的 L-tree，
右子树为 order m-2 的 L-tree
3. 若 order为 m 的 L-tree 用阵列表示，则其结构为
[ left subtree | right subtree | root ]
Leonardo Heap 是一组 L-trees 的集合并满足以下性质：
1. 所有的 L-tree 皆满足 minimum-heap property
2. 不存在重覆 order 的 L-tree
3. 只能最小两个 order 的 L-tree 差是 1
4. 最小 order 的 L-tree 的 root 是 Leonardo Heap 的最小值
再来说明一下 Leonardo Heap 的操作
假设插入一个新元素 x ，则可以分两种情况：
1. 若最小 order 的 L-tree Ta 与次小 order 的 L-tree Tb 的 order 差 1
把 Ta 、 Tb 、 x 合成新的 L-tree Tc 进 Leonardo Heap ， Tc
需满足 minimum-heap property
2. 否则把 x 设为 size 1 的 L-tree 加进 Leonardo Heap
假设加入前的最小 order 的 L-tree 为 Ta
若 Ta 的 root < x ， 则交换两个 L-tree 的 root 并调整 Ta 使其
满足 minimum-heap property，反之不交换。
由此可知插入的时间复杂度为 O(log n)
关於 Leonardo Heap 的删除最小值：
假设最小 order 的 L-tree 为 Ta
1.a 若 Ta 的 size 为 1，则把 Ta 从 Leonardo Heap 移除
1.b 反之把 Ta 的 root 移除，使其分解成两个 L-tree 加入 Leonardo Heap 中
2. 假设在新的 Leonardo Heap 中，最小 order 的 L-tree 为 Ta'，
有最小root的 L-tree 为 Tb'。不失一般性，让 Ta' 不等於 Tb'。
则我们交换 Ta' 与 Tb' 的 root，并调整 Tb'使其满足
minimum-heap property
因此删除最小值的时间复杂度为 O(log n)
Amortized analysis
For given a Leonardo Heap H{i} = { L{k, i} | L{k, i} is the L-tree
with the k-th smallest order in i-th operation } in i-th operation
Let n{i} be the number of H{i}
h(L{k, i}) be height of L{k, i}
s(H{i}) be the number of L-tree in H{i}
Define a potential function phi(D{i}) for data structure state D{i}
1. phi(D{0}) = 0
2. phi(D{i}) = 0 if n{i} = 0
3. phi(D{i}) = sum { h(L{k, i}) } + h(L{1, i}) if n{i} > 0
The insertion analysis :
case 1 :
Let h(L{1, i - 1}) = t, h(L{2, i - 1}) = t + 1
ci = h(L{1, i - 1}) + 1
= t + 1
phi(D{i}) - phi(D{i - 1}) = ((t + 2) + (t + 2)) - ((t + 1) + t + t)
= 3 - t
ci' = ci + (phi(D{i}) - phi(D{i - 1}))
= (t + 1) + (3 - t)
= 4
case 2 :
Let h(L{1, i - 1}) = t
ci = h(L{1, i - 1}) + 1
= t + 1
phi(D{i}) - phi(D{i - 1}) = (t + 1 + 1) - (t + t)
= 2 - t
ci' = ci + (phi(D{i}) - phi(D{i - 1}))
= (t + 1) + (2 - t)
= 3
Hence, the insertion operation take O(1) amortized time.
The deletion analysis :
Let h(L{1, i - 1}) = t, h(L{2, i - 1}) = m
Assume W.L.O.G that second smallest element is the root of
L{x, i - 1} where x != 1
ci = h(L{x, i - 1}) + s(H{i}) + 1
Trivially, h(L{x, i - 1}) <= m1 * log(n{i})
s(H{i}) <= m2 * log(n{i})
for some constant m1, m2
So we know ci <= (m1 + m2 + 1) * log(n{i})
if t = 1, then
phi(D{i}) - phi(D{i - 1}) = (m + m) - (m + 1 + 1)
= m - 2
<= c1 * log(n{i})
for some constant c1
otherwise,
phi(D{i}) - phi(D{i - 1}) = ((t - 1) + (t - 2) + (t - 2)) - (t + t)
= t - 5
<= c2 * log(n{i})
for some constant c2
ci' = ci + phi(D{i}) - phi(D{i - 1})
<= (m1 + m2 + 1 + max{c1, c2}) * log(n{i})
Therefore, the deletion operation take O(log(n)) amortized time.
结论
Leonardo Heap 的插入 amortized time complexity 是 O(1)，然後删除
amortized time complexity 是 Θ(log n)
参考资料
https://en.wikipedia.org/wiki/Smoothsort
--
d(・ω・d) 微分！ (∫・ω・)∫ 积分！ ∂(・ω・∂) 偏微分！
(∮・ω・)∮ 沿闭曲线的积分！ (∬・ω・)∬ 重积分！ ▽(・ω・▽)梯度！
▽・(・ω・▽・)散度！ ▽×(・ω・▽×)旋度！ Δ(・ω・Δ)拉普拉斯!
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.235.150.165
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1557850377.A.9AE.html
1F：推 FRAXIS: 删除的 amortized time complexity 直接被 worst case 05/15 10:55
2F：→ FRAXIS: imply 应该不用证明吧？ 05/15 10:55
3F：→ FRAXIS: 而且 amortized time complexity 应该有 log n 的下限 05/15 10:56
4F：→ firejox: 因为我想把各种情况都考虑进去，所以连删除的也列了 05/15 15:36
5F：→ firejox: 另外你说的log n的下限有点不太懂 05/15 15:37
6F：推 FRAXIS: 插入已经是 amortized O(1) 了 05/16 10:42
7F：→ FRAXIS: 删除 amortized 一定是 Ω(lg n) 05/16 10:43
8F：→ FRAXIS: 不然就可以设计 o(n lg n) 的 comparison-based 排序法了 05/16 10:44
9F：→ FRAXIS: 所以删除的 amortized 是 Θ(lg n) 05/16 10:45
10F：→ firejox: 了解 05/16 17:47
※ 编辑: firejox (36.235.148.14), 05/21/2019 21:19:58