3

我正在尝试了解 Leader-Follower 算法的复杂性。这是算法的最坏情况：

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 部分，但是我无法确定如何计算内部循环的复杂性。

编辑：关于领导者-跟随者算法的简短信息：该算法是一种在线聚类算法，用于对数据流进行聚类，不需要定义聚类的数量。该算法接受数据输入和阈值。该算法的工作原理如下：

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

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

4

2 回答 2

2

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

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

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

希望这可以帮助！

于 2013-06-13T18:32:02.253 回答
0

形式上，答案可以描述如下（其中n = array.length）：

在此处输入图像描述

于 2014-03-14T03:37:35.407 回答