performance - leader-follower算法的时间复杂度？

Question

我试图了解领导者-追随者算法的复杂性。这是该算法的最坏情况:

public class ScalabilityTest {

public static void main(String[] args) {
    long oldTime = System.currentTimeMillis();
    double[] array = new double[5000000];

    for ( int i = 0; i < array.length; i++ ) {
        for ( int j = 0; j < i; j++ ) {
            double x = array[j] + array[i];
        }
    }

    System.out.println( (System.currentTimeMillis()-oldTime) / 1000 );
}

}

我假设复杂度为 O(N*Log(N))，对吗？第一个 N 部分是我确定的，因为第一个循环，但是我无法确定如何计算内部循环的复杂度。

编辑:关于leader-follower算法的简短信息:该算法是一种在线聚类算法，用于对数据流进行聚类，无需定义聚类数。该算法接受数据输入和阈值。该算法的工作原理如下:

1-它计算传入项目与所有现有集群的相似度2-如果项目和集群之间的相似性高于阈值，则将项目添加到集群中。3- 如果不是，该算法将创建一个新集群并将项目分配给该集群。

从中我们可以看到最坏的情况:假设我们有 1000 个元素，并且假设对于每个传入的项目，它找不到一个集群来分配它，那么在最后一次迭代时它将以 1000 个集群结束。

Answer 1

该算法的复杂度为 Θ(n²)。要看到这一点，请注意，当 i = 0 时，内部循环将运行 0 次迭代，当 i = 1 时，将运行 1 次迭代，当 i = 2 时，将运行 2 次迭代，等等。如果你对从 0 到 n - 1 的 i 求和，你得到

0 + 1 + 2 + ... + (n - 1) = n(n - 1)/2 = Θ(n²)

因此，总运行时间为 Θ(n²)。您会在选择排序和(最坏情况)插入排序的分析中看到与此类似的分析，因为这些算法中的每一个都执行 1 + 2 + ... + n 的工作。

希望这对您有所帮助!