performance - リーダーフォロワーアルゴリズムの時間の複雑さは?

Question

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 個のクラスターになることになります。

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 が機能するため、これと同様の分析が見られます。

お役に立てれば！

Answer 2

正式には、答えは次のように表すことができます ( n = array.length )。