作者love52697 (sillyboy)
看板Grad-ProbAsk
标题[理工] 资结disjoint set时间复杂度
时间Tue Nov 13 18:55:33 2018
各位大大好,关於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次就好了吗?@@
就算是要生出n的元素,把他们都接上另一个已经存在的集合
最多也就接n次而已
为甚麽要用这种迂回的方式推出一个好像不是tight bound的结果呢?
我觉得可能无论是theorem本身或证明我的理解都有问题
但我看了好几遍还是觉得他是这个意思
还请各位强者们不吝指教, 非常感谢!!
对了, 文章是在cormen p566, p567
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.137.200.212
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1542106536.A.3E5.html
※ 编辑: love52697 (61.230.200.176), 11/13/2018 20:04:40
1F：推 eggy1018: 接n次，但是处理的东西是他是属於什麽set，指的是更新他 11/14 02:21
2F：→ eggy1018: 所属的set值，每一次接都要处理logn个node，所以时间复 11/14 02:21
3F：→ eggy1018: 杂度一共O(nlogn) 11/14 02:21
4F：→ eggy1018: 以上是小弟的见解，有错还请告知 11/14 02:21
5F：→ love52697: 这也是我觉得我可能想错但不知道错在哪里的地方 11/14 12:45
6F：→ love52697: 我一直以为在weight-union下接上一个元素是O(1) 11/14 12:50
7F：→ love52697: 因为总是短的并入长的, 11/14 12:51
8F：→ love52697: 以我们讨论的case就是把一个个新生的单一node并入原有 11/14 12:52
9F：→ love52697: 的set 11/14 12:52
10F：→ love52697: 从link list的接法来看, 11/14 12:53
11F：→ love52697: 想多并入一个node只要从set的最後面接上就好了, 11/14 12:54
12F：→ love52697: 不需要动到set里其他node的set值 11/14 12:55
14F：推 eggy1018: 对 但是他的logn是来自”每次被更新set的节点数” 有点 11/14 13:35
15F：→ eggy1018: 像Dij decreases key的感觉 11/14 13:35
16F：→ love52697: 如果用weighted-union的方式一个一个接起来, 11/14 21:50
17F：→ love52697: 每次Union的时候被更新的set都是只有一个节点的那个set 11/14 21:51
18F：→ love52697: 啊 11/14 21:51
19F：→ love52697: 这样每次更新的节点数都是1,但我注意到另一个问题, 11/14 21:51
20F：→ love52697: 就是每次接的时候都要寻找长的set的最後一个节点 11/14 21:51
21F：→ love52697: 若把这个时间算进去这种接法的总时间就会是O(n^2) 11/14 21:52
22F：→ love52697: 倒不如两两一组接,总时间就会是O(nlogn)我这样想不知道 11/14 21:52
23F：→ love52697: 对不对? 11/14 21:52