作者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/m.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