[問題] Single-Link Clustering 的 time complexity
為什麼會是 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
推
140.116.231.175 03/18, , 1F
140.116.231.175 03/18, 1F
推
140.116.231.175 03/18, , 2F
140.116.231.175 03/18, 2F
→
140.116.231.175 03/18, , 3F
140.116.231.175 03/18, 3F
→
140.116.231.175 03/18, , 4F
140.116.231.175 03/18, 4F
→
140.116.231.175 03/18, , 5F
140.116.231.175 03/18, 5F
推
220.130.197.238 03/18, , 6F
220.130.197.238 03/18, 6F