0

以下のようなコードを書きましたが、このアルゴリズムの複雑さが O(n) なのか O(n 2 ) なのか混乱しています。誰でも私を確認してもらえますか？

  for(int i=0, j=i+1;i<array.length;j++)
    {

        if(j==array.length)
        {
            if(array[i]==3)
                System.out.println(array[i]);
            i++;                
            j=i;
            continue;
        }

        int k=array[i]+array[j];
        if(k==3)
        {
            System.out.println("{"+array[i]+","+array[j]+"}");
        }

    }
4

5 に答える 5

2

ですO(n^2)。配列全体を実行したi後にのみインクリメントされます。jこれは、ループの反復ごとに発生し、反復ごとに入力が 1 小さくなります。つまりn*(n-1)/2、 ですO(n^2)。

于 2013-07-28T13:24:27.873 に答える
2

ですO(n^2)。

で始まるi=0: for j = 1 -> array.length => n 回の繰り返し

ステップ 2: i = 1 => for j = 2 -> array.length => n - 1 反復

...

ステップ n - 1: i = array.length - 2 => for j = array.length - 1 -> array.length => 1 回の反復

したがって、複雑さはn * (n + 1) / 2であり、これはn^2です。

于 2013-07-28T13:27:58.353 に答える
1

これは O((n(n+1))/2)

これは O(n^2)

于 2013-07-28T13:23:33.807 に答える