[問題] Single-Link Clustering 的 time complexity

[owenlin (Owen)]

為什麼會是 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
推 Eventis:這個網頁交代的很清楚了啊@@
推 Eventis:只要看到前一句
→ Eventis:update the distance matrix in O(n)
→ Eventis:最小的distance就是next best merge
→ Eventis:但是為了更新這個資料同樣也要花O(n)
推 owenlin:謝啦！我懂了…… ^^