作者ok8752665 ()
看板Grad-ProbAsk
標題[理工] 資結 winner/loser tree
時間Wed Jan 29 16:01:17 2020
剛翻筆記的時候看到說
這兩個的時間複雜度一樣
但會選用loser 因參與比較點數較少 後只需和父點比較
可是我看了一下
winner後面也只需要跟sibling比
具體來說 loser是少了哪些比較阿
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.38.74.199 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1580284880.A.5D3.html
1F：→ MASAGA: winner tree要全部重比 01/29 16:35
2F：→ MASAGA: loser tree只有輸出的那條array需要往上重比(跟parent) 01/29 16:35
3F：→ zuchang: delete min 的時候 winner要log k 但loser 只要O1 01/29 16:37
4F：→ MASAGA: loser tree在delete min後不用花O(logn)維持嗎@@ 01/29 16:59
5F：→ bochengchen: winner tree 維持是O(n) loser tree是 O(logk) 吧 01/29 17:38
6F：→ ok8752665: 複雜度不一樣嗎? 01/29 18:19
7F：→ gcobc19622: 兩個時間一樣吧，只差在參與節點數loser比較少 01/29 18:23
8F：→ gcobc19622: 比較次數應該是一樣，只是一個是跟parent比，一個是 01/29 18:26
9F：→ gcobc19622: 跟sibling 01/29 18:26
10F：→ ok8752665: 參與結點是什麼意思 為什麼比較次數一樣但參與結點較少 01/29 19:23