[理工] 資結 winner/loser tree

看板Grad-ProbAsk作者時間5年前 (2020/01/29 16:01), 編輯推噓0(0推 0噓 10→)
留言10則, 5人參與, 5年前最新討論串1/1
剛翻筆記的時候看到說 這兩個的時間複雜度一樣 但會選用loser 因參與比較點數較少 後只需和父點比較 可是我看了一下 winner後面也只需要跟sibling比 具體來說 loser是少了哪些比較阿 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.38.74.199 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1580284880.A.5D3.html
→
01/29 16:35, 5年前 , 1F
winner tree要全部重比
01/29 16:35, 1F
→
01/29 16:35, 5年前 , 2F
loser tree只有輸出的那條array需要往上重比(跟parent)
01/29 16:35, 2F
→
01/29 16:37, 5年前 , 3F
delete min 的時候 winner要log k 但loser 只要O1
01/29 16:37, 3F
→
01/29 16:59, 5年前 , 4F
loser tree在delete min後不用花O(logn)維持嗎@@
01/29 16:59, 4F
→
01/29 17:38, 5年前 , 5F
winner tree 維持是O(n) loser tree是 O(logk) 吧
01/29 17:38, 5F
→
01/29 18:19, 5年前 , 6F
複雜度不一樣嗎?
01/29 18:19, 6F
→
01/29 18:23, 5年前 , 7F
兩個時間一樣吧，只差在參與節點數loser比較少
01/29 18:23, 7F
→
01/29 18:26, 5年前 , 8F
比較次數應該是一樣，只是一個是跟parent比，一個是
01/29 18:26, 8F
→
01/29 18:26, 5年前 , 9F
跟sibling
01/29 18:26, 9F
→
01/29 19:23, 5年前 , 10F
參與結點是什麼意思 為什麼比較次數一樣但參與結點較少
01/29 19:23, 10F
‣ 更多 ok8752665 的文章
文章代碼(AID): #1UCJlGNJ (Grad-ProbAsk)