dist（）的复杂性是什么？

Question

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

我知道层次聚类的时间复杂度为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加法。