[理工] 资结 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

参与结点是什么意思为什么比较次数一样但参与结点较少

继续阅读