两个或多个for循环时间复杂度

Question

如果我们假设 for 循环内的语句是 O(1)。

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

那么上面的时间复杂度应该是o(n) 另一个例子是：

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

上面的时间复杂度应该是o(n^2)

好像是一个for循环符号n次但是，我看到一些讨论说它不只是这样有时有2个for循环，但这并不意味着时间复杂度必须是o(n^2)

谁能给我一个只有 O(n) 时间复杂度的两个或更多 for 循环的例子（有解释会更好）？？？

Answer 1

如果边界是固定的，循环可以有固定的时间。所以对于这些嵌套循环，其中 k 是一个常量：

// k is a constant
for (int i=0; i<N; i++) {
  for (int j=0; j<k; j++) {
  }
}

// or this
for (int i=0; i<k; i++) {
  for (int j=0; j<N; j++) {
  }
}

都是O(kN)~=O(N)

post中的代码的时间复杂度为：

鉴于这是一个二阶多项式 (N^2 - N)/2，您正确评估了示例的渐近时间复杂度为 O(N^2)。

Answer 2

当外循环或内循环在迭代中受到固定限制（常数值）的限制时，就会发生这种情况。它在许多问题中经常发生，比如位操作。像这样的例子：

for (int i = 0; i < n; i++) {
    int x = ...;      //some constant time operations to determine int x
    for (int j = 0; x != 0; j++) {
        x >>>= 1;
    }
}

内部循环受限于 int 的位数。对于Java，就是32，所以内层循环严格限制在32次迭代，是常量时间。复杂度是线性时间或 O(n)。

两个或多个for循环时间复杂度

two or more for loops time complexity

algorithm

for-loop

time-complexity