如何找到嵌套for循环的时间复杂度

Question

下面所示的嵌套循环的时间复杂度是多少：

1)

for (int i = 1; i <=n; i += 2) {
    for (int j = 1; j <=n; j += 2) {
        // some O(1) expressions
    }
}

2)

for (int i = 1; i <=n; i += 3) {
    for (int j = 1; j <=n; j += 3) {
        // some O(1) expressions
    }
}

总的来说：

for (int i = 1; i <=n; i += c) {
   for (int j = 1; j <=n; j += c) {
      // some O(1) expressions
   }
}

真的是下面这个吗？

O(n^c)

Answer 1

一般情况下，内循环复杂度为O(n)，外循环复杂度为O(n)。因此，对于外部循环的每次迭代，内部循环迭代 n 次（c 对于复杂度的顺序无关紧要，应该被视为 1）。如果外层循环迭代n次，则内层循环的总迭代次数为n*n，即O(n^2).

Answer 2

假设有 10 把椅子（n 在这里）在一个 for 循环中，你正在遍历所有的椅子，假设你坐在所有的椅子上，所以在给定的循环中你总共需要坐 10 次才能坐在所有的椅子上。

现在假设你坐在第一把椅子上，让你的朋友一张一张地坐在其他椅子上，包括你的椅子，所以你的朋友总共要坐 10 把椅子。现在你选择了第二把椅子，又让你的朋友每张椅子都坐一次，所以他总共要坐10把椅子。

同样你可以选择第3、4...把椅子等等，所以你的朋友总共要为你选择的每把椅子坐10把椅子。

10 + 10 + ... = 100 次

相当于 10^2 = 100

所以复杂度是O(n^2)，其中n是椅子的数量。

Answer 3

您的算法将执行 (n / c) * (n /c) 次迭代。我们正在除法，因为我们在每次迭代中跳过 c 个字符。看到那个：

for (var i = 0; i <= n; i = i + 1)

将有 n / 1 次迭代

for (var i = 0; i <= n; i = i + 2)

将有 n / 2 次迭代

_{*请注意，结果会被打倒。即如果n = 3和c = 2，则只执行一次(floor(3 / 2) == 1)}

所以，我们可以概括为

(n / c)²
= (n²/c²) 
= 1/c² * n²

记住 Big O 只对变化率感兴趣。由于 c 是常数，因此在计算中将其忽略。

所以，结果是：

O(1/c² * n²) = O(n²)

How to find the time complexity of nested for-loop