[理工] 資結disjoint set時間複雜度

[love52697 (sillyboy)]

各位大大好,關於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://www.ptt.cc/bbs/Grad-ProbAsk/M.1542106536.A.3E5.html
※ 編輯: love52697 (61.230.200.176), 11/13/2018 20:04:40
推 eggy1018: 接n次，但是處理的東西是他是屬於什麼set，指的是更新他
→ eggy1018: 所屬的set值，每一次接都要處理logn個node，所以時間複
→ eggy1018: 雜度一共O(nlogn)
→ eggy1018: 以上是小弟的見解，有錯還請告知
→ love52697: 這也是我覺得我可能想錯但不知道錯在哪裡的地方
→ love52697: 我一直以為在weight-union下接上一個元素是O(1)
→ love52697: 因為總是短的併入長的,
→ love52697: 以我們討論的case就是把一個個新生的單一node併入原有
→ love52697: 的set
→ love52697: 從link list的接法來看,
→ love52697: 想多併入一個node只要從set的最後面接上就好了,
→ love52697: 不需要動到set裡其他node的set值
→ love52697: https://i.imgur.com/ITIIpwQ.jpg
推 eggy1018: 對 但是他的logn是來自”每次被更新set的節點數” 有點
→ eggy1018: 像Dij decreases key的感覺
→ love52697: 如果用weighted-union的方式一個一個接起來,
→ love52697: 每次Union的時候被更新的set都是只有一個節點的那個set
→ love52697: 啊
→ love52697: 這樣每次更新的節點數都是1,但我注意到另一個問題,
→ love52697: 就是每次接的時候都要尋找長的set的最後一個節點
→ love52697: 若把這個時間算進去這種接法的總時間就會是O(n^2)
→ love52697: 倒不如兩兩一組接,總時間就會是O(nlogn)我這樣想不知道
→ love52697: 對不對?