dist() 的复杂度是多少？
What is the complexity of dist()?
我在 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 复杂性？
准确地说，如果矩阵 X 有 N 行 P 列，则 dist(X) 的复杂度是 3N(N-1)P/2。这是由 N(N - 1)/2 * 3P.
计算得出的
解释：
- 结果距离矩阵中有
N(N - 1)/2 个条目；
- 每个条目都是两个长度
P 向量（加上一个平方根）之间的点积，每个向量都涉及 P 减法、P 乘法和 P 加法。
我在 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 复杂性？
准确地说，如果矩阵 X 有 N 行 P 列，则 dist(X) 的复杂度是 3N(N-1)P/2。这是由 N(N - 1)/2 * 3P.
解释：
- 结果距离矩阵中有
N(N - 1)/2个条目； - 每个条目都是两个长度
P向量（加上一个平方根）之间的点积，每个向量都涉及P减法、P乘法和P加法。