performance - 別々に2回ループすることと、ループ内でループすることの間のパフォーマンス

Question

2回別々にループすることとループ内でループすることの間にパフォーマンスの違いはありますか？それを証明または計算する方法は？

Answer 1

それは完全にループに依存します。O(n^2)実行時間の例を次に示します。

1) Nested loops to n

for(i from 1 to n){
    for(j from 1 to n){
        ...
    }
}

2) Nested loops to n with the inner loop starting from i

for(i from 1 to n){
    for(j from i to n){
        ...
    }
}

3) Second loop iterates n^2 times since i == n

for(i from 1 to n){
    ...
}
for(j from 1 to i*n){
    ...
}

4) One loop up to n*n/50

for(i from 1 to n*n/50){
    ...
}

O(n)ループの例を次に示します。

1) Simple loop

for(i from 1 to n){
    ...
}

2) Nested loop with constant iterations

for(i from 1 to n){
    for(j from 1 to 5){
        ...
    }
}

n次に、へのループのように、より良い時間計算量が十分に小さい場合に常に高速であるとは限らないという事実がありますn*n/50。nが（正の整数）未満の場合8、そのループはまったく反復されないため、O(n)正確なn回数反復する単純なループよりも明らかに高速になります。

Answer 2

一般的に言えば：

長さ（および ）O(n + m)が異なる2つの異なるループがある場合が考えられます。nm

for (int i = 0; i < n; i++) {}
for (int i = 0; i < m; i++) {}    

O(n * m)ループ内でループしている可能性があります。

for (int i = 0; i < n; i++) {
   for (int j = 0; j < m; j++) {
   }
}