r - dist() 的复杂度是多少？

Question

我dist在 R 中使用了这个函数，我想知道它的时间复杂度。

我知道层次聚类具有N^2*logN时间复杂度。层次聚类由两部分组成，如下R中的代码。

> d <- dist(as.matrix(mtcars))   # find distance matrix 
> hc <- hclust(d)                # apply hirarchical clustering 
> plot(hc)                       # plot the dendrogram

在应用层次聚类之前，需要计算距离矩阵。我认为这需要N^2复杂性？

Answer 1

准确地说，如果矩阵X有N行列P，则复杂度dist(X)为3N(N-1)P/2。这是由 计算的N(N - 1)/2 * 3P。

解释：

• 结果距离矩阵中有N(N - 1)/2条目；
• 每个条目是两个长度P向量（加上平方根）之间的点积，每个向量都涉及P减法、P乘法和P加法。