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加法。