作者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/cn.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