推 FRAXIS:Array做Decrease-Key只要修改值就好所以是O(1) 03/10 12:22
→ FRAXIS:Heap還要做調整 往root的方向調整 最多只要調整O(lgn)次 03/10 12:23
→ FRAXIS:Fibonacci Heap是因為用Amortized Analysis的關係.. 03/10 12:23
→ Lautreamont:對喔 用heap還是要調整 感激!!! 03/10 12:30
97年交大有一題關於實作Dijkstra's algo的min-priority queue
然後我看了一下Cormen的說明，感覺不是很懂，所以希望可以指點我一下
謝謝
(1) Linear search找最小的點
每次執行Extract-Min耗時: O(|V|)
全部vertex做一次: O(|V|)
全部Dcrease-Key耗時: O(|E|) (with adjacent list)
TOTAL: O(|V|*|V|+|E|) = O(|V|^2+|E|)
(2) 用Binary Min Heap
每次執行Extract-Min耗時: O(log|V|)
建立Min-Heap耗時: O(|V|)
每次Dcrease-Key耗時: O(log|V|) (這裡是怎麼來的??????)
Dcrease-Key全部最多做|E|次
TOTAL: O((|V|+|E|)*log|V|)
請問在(1)中Dcrease-Key是不是每次皆花O(1)的時間?
所以最多|E|次，總共花O(|E|)
如果上面的想法正確，則(1)、(2)的TOTAL可以寫成:
(1) O( |V|*|V| + |E|*1 )
^^^^ ^^每次Dcrease-Key
每次Extract-Min
(2) O( (|V|*log|V| + |E|*log|V| )
^^^^ ^^^^^^每次Dcrease-Key
每次Extract-Min
請問為什麼原來每次deacrease key要O(1) (我自己的假設)
用了Binary Min Heap之後卻要O(log|V|)
然後用Fibonacci Heap後又回到O(1) ?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.136.244.169