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