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