PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[心得] Leonardo Heap的 amortized analysis

看板Prob_Solve (計算數學 Problem Solving)作者firejox (Tangent)時間5年前 (2019/05/15 00:12)推噓2(2推 0噓 8→)

留言10則, 2人參與討論串1/1

因為對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://www.ptt.cc/bbs/Prob_Solve/M.1557850377.A.9AE.html