作者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