作者owenlin (Owen)
看板CSSE
標題[問題] Single-Link Clustering 的 time complexity
時間Fri Mar 18 12:49:42 2005
為什麼會是 O(n^2) 呢？
這裡有一個這樣的演算法說明：
http://www-csli.stanford.edu/~schuetze/completelink.html
簡單來說，就是對每一個 cluster 保持 一個 next_best_merge 的 link，
當兩個 cluster 合併時，就去 update 所有的 next_best_merge ，
因為，如果 cluster i 和 cluster j merge 的話，
而 cluster k 之前的 best merge 是 i 或 j ，
那它的新 best merge 就是 新的 cluster
反之就不受影響。
不只這個網頁這麼說，以前也有個 reviewer 也和我說類似的解法，
但是 如果 merge i 和 j 的話，
那麼這個新的 cluster 的 next-best-merge 要怎麼算呢？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.130.197.238
1F：推 Eventis:這個網頁交代的很清楚了啊@@140.116.231.175 03/18
2F：推 Eventis:只要看到前一句140.116.231.175 03/18
3F：→ Eventis:update the distance matrix in O(n)140.116.231.175 03/18
4F：→ Eventis:最小的distance就是next best merge140.116.231.175 03/18
5F：→ Eventis:但是為了更新這個資料同樣也要花O(n)140.116.231.175 03/18
6F：推 owenlin:謝啦！我懂了…… ^^220.130.197.238 03/18