[理工] 資結 winner/loser tree ok8752665 PTT批踢踢實業坊

作者: ok8752665 (dd8752665) 2020-01-29 16:01:17

剛翻筆記的時候看到說
這兩個的時間複雜度一樣
但會選用loser 因參與比較點數較少後只需和父點比較
可是我看了一下
winner後面也只需要跟sibling比
具體來說 loser是少了哪些比較阿

作者: MASAGA (和泉千晶我老婆) 2020-01-29 16:35:00

winner tree要全部重比loser tree只有輸出的那條array需要往上重比(跟parent)

作者: zuchang (chang) 2020-01-29 16:37:00

delete min 的時候 winner要log k 但loser 只要O1

作者: MASAGA (和泉千晶我老婆) 2020-01-29 16:59:00

loser tree在delete min後不用花O(logn)維持嗎@@

作者: bochengchen (LFII) 2020-01-29 17:38:00

winner tree 維持是O(n) loser tree是 O(logk) 吧

作者: ok8752665 (dd8752665) 2020-01-29 18:19:00

複雜度不一樣嗎?

作者: gcobc19622 2020-01-29 18:23:00

兩個時間一樣吧，只差在參與節點數loser比較少比較次數應該是一樣，只是一個是跟parent比，一個是跟sibling

作者: ok8752665 (dd8752665) 2020-01-29 19:23:00

參與結點是什麼意思為什麼比較次數一樣但參與結點較少

繼續閱讀