performance - 分别循环两次和在一个循环内循环之间的性能

Question

分别循环两次和在一个循环内循环之间有什么性能差异吗？如何证明或计算？

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. If nis less than 8(a positive int) 则该循环根本不会迭代，因此它显然比具有 的 Simple 循环更快O(n)，后者将精确地迭代n次数。

Answer 2

通常来说，一般来说：

O(n + m)如果您有两个不同长度的不同循环（n和 m） ，则可能是这样。

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++) {
   }
}