[問題] Fibonacci Heap相關證明
看板Prob_Solve (計算數學 Problem Solving)作者mqazz1 (無法顯示)時間14年前 (2010/10/03 21:17)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/1
Let a be an F-heap with n elements that results from a sequence of insert,
meld, delete min, and decrease key operations performed on initially empty
F-heap.
Let b be any node in any of the min-trees of a
the degree of b is at most log(φ)(m) // 以φ為底
where φ = ( 1 + √5 ) / 2
m is the number of elements in the subtree with root b.
請問要怎麼證明the degree of b is at most log(φ)(m)呢?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.166.113.243
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
