[理工] 資結disjoint set時間複雜度
各位大大好,關於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
我對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
推
11/14 02:21,
7年前
, 1F
11/14 02:21, 1F
→
11/14 02:21,
7年前
, 2F
11/14 02:21, 2F
→
11/14 02:21,
7年前
, 3F
11/14 02:21, 3F
→
11/14 02:21,
7年前
, 4F
11/14 02:21, 4F
→
11/14 12:45,
7年前
, 5F
11/14 12:45, 5F
→
11/14 12:50,
7年前
, 6F
11/14 12:50, 6F
→
11/14 12:51,
7年前
, 7F
11/14 12:51, 7F
→
11/14 12:52,
7年前
, 8F
11/14 12:52, 8F
→
11/14 12:52,
7年前
, 9F
11/14 12:52, 9F
→
11/14 12:53,
7年前
, 10F
11/14 12:53, 10F
→
11/14 12:54,
7年前
, 11F
11/14 12:54, 11F
→
11/14 12:55,
7年前
, 12F
11/14 12:55, 12F
→
11/14 12:55,
7年前
, 13F
11/14 12:55, 13F
推
11/14 13:35,
7年前
, 14F
11/14 13:35, 14F
→
11/14 13:35,
7年前
, 15F
11/14 13:35, 15F
→
11/14 21:50,
7年前
, 16F
11/14 21:50, 16F
→
11/14 21:51,
7年前
, 17F
11/14 21:51, 17F
→
11/14 21:51,
7年前
, 18F
11/14 21:51, 18F
→
11/14 21:51,
7年前
, 19F
11/14 21:51, 19F
→
11/14 21:51,
7年前
, 20F
11/14 21:51, 20F
→
11/14 21:52,
7年前
, 21F
11/14 21:52, 21F
→
11/14 21:52,
7年前
, 22F
11/14 21:52, 22F
→
11/14 21:52,
7年前
, 23F
11/14 21:52, 23F