12

私は StackOverflow で少し検索し、j ループのポイントまでの複雑さを理解しました。ただし、k ループのネストされた追加により、なぜ複雑になるのか混乱しています。誰かがこれを理解するのを手伝ってくれますか?O(n2)O(n3)

私の理解では、i ループには n 回の反復があり、j ループには 1+2+3+...+n 回の反復n*(n+1)/2があります。O(n2)

for(i = 1; i < n; i++) {   
    for(j = i+1; j <= n; j++) {
        for(k = i; k <= j; k++) {
           // Do something here...
        }
    }
}

編集:助けてくれてありがとう:) バルタザール、どのループにいるかに応じてカウンターをインクリメントするコードを書きました。

#include <iostream>

int main(int argc, const char * argv[])
{
    int n = 9;
    int index_I = 0;
    int index_J = 0;
    int index_K = 0;
    for (int i = 1; i < n; i++) {
        for (int j = i+1; j <= n; j++) {
            for (int k = i; k <= j; k++) {
                index_K++;
            }
            index_J++;
        }
        index_I++;
    }
    std::cout << index_I << std::endl;
    std::cout << index_J << std::endl;
    std::cout << index_K << std::endl;
    return 0;
}

このコードを n=2 から n=9 まで 1 ずつ増やして実行したところ、次のシーケンスが得られました。

したがって、カウンタから次のことがわかります。 i = n-1 は O(n) の複雑さを示し、j = ((n-1)*n)/2 は複雑さを示します。K のパターンを見つけるのは困難でしたが、K が J に依存することが知られているため、次のようになります。O(n2)

k = ((n+4)/3)*j = (n*(n-1)*(n+4))/6の複雑さを与えるO(n3)

これが将来人々に役立つことを願っています。

EDIT2: 書式設定についてDukelingに感謝します:) また、最後の行に間違いが見つかりました。現在修正されています。

4

5 に答える 5

7

k ループの複雑さは O(ji) です

jループの複雑さはO((ni)*(ni))です

i ループの複雑さは O(n*n*n)=O(n^3) です

とにかく、最初の 2 つのループが O(n^2) であるため O(n^2) ではなく、ループが 3 つしかないため O(n^3) を超えないことがわかります。

于 2013-08-28T11:31:47.337 に答える
2

最悪の場合の複雑さを評価するために、この例を見てください。

本質的に、行ごとに評価すると、O(n^3 / C) のような結果になります。ここで、C は定数であり、通常、そのような評価ではスキップされ、O(n^3) になります。

于 2013-08-28T11:31:16.533 に答える
1

最初に、内側のループの反復回数が外側のループのインデックスの値に依存しないループを考えます。例えば：

for (i = 0; i < N; i++) {
      for (j = 0; j < M; j++) {
             sequence of statements
      }
  }

外側のループは N 回実行されます。外側のループが実行されるたびに、内側のループが M 回実行されます。その結果、内側のループ内のステートメントは合計 N * M 回実行されます。
したがって、2 つのループの合計の複雑さは O(N2) です。
同様に、3 つのループの複雑度は O(N3) です。

于 2014-04-29T10:19:02.360 に答える
1

これは、図なしで説明するのは非常に難しいですが、ネストされた各ループは、反復を親に返す前に「n」回反復します。

したがって、jambono が指摘するように、ネストされた各ループでは、「n」の反復ごとに比較/評価が必要です。そのため、「n」は各ループ (n*n*n) でローカル変数と比較され、O(n^3) になります。

この複雑さがマシンによってどのように処理されるかを視覚的に示すために、デバッガーでコードをステップ実行します。

于 2013-08-28T11:41:08.120 に答える