各位大大好,关于disjoint set以link list的形式,在weighted-union的方式下做
"a sequence of m MAKE-SET, UNION, and FIND-SET operations, n of which are MAK
E-SET operations"
的时间复杂度,小弟有个问题想请教
附图是cormen书谈到这个的部分
https://i.imgur.com/G5VRkN0.jpg
https://i.imgur.com/QbszVe4.jpg
我对Theorem 21.1的理解是有m个operation,
其中有n个是Make-Set,
所以有n-1个是Union,有m-2n+1个是Find-Set
求这m个operation的总时间复杂度
证明所有Union的时间复杂度为nlog(n)的部分我很困惑,
我对书上写的理解是,
在形成一个有n个元素集合的过程中,
每个元素最多被处理log(n)次,
所以总共最多需要nlog(n)次的时间
我的困惑点在于,
不是只要一个一个依序接起来总共接n-1次就好了吗[email protected]@
就算是要生出n的元素,把他们都接上另一个已经存在的集合
最多也就接n次而已
为什么要用这种迂回的方式推出一个好像不是tight bound的结果呢?
我觉得可能无论是theorem本身或证明我的理解都有问题
但我看了好几遍还是觉得他是这个意思
还请各位强者们不吝指教, 非常感谢!!
对了, 文章是在cormen p566, p567