如何计算这段代码的时间复杂度？

Question

下面算法的时间复杂度如何计算？

int x =0;

      for (int i = 1; i < n; i++) {

        for (int j = 1; j < n; ++j) {
            x++;
            n--;
        }
    }

我知道嵌套for循环的时间复杂度等于最内层循环执行的次数。

就像外循环从 1 到 n 的每个嵌套循环一样，它应该运行 n 次，但这里我们有 n-- 使算法运行的顺序更好。实际上，我在 IDE 中编写了这段代码，并且在不同的 n 值循环结束后打印了 x 的最终结果，我看到将近 n 次我们跳入内部 for 循环。

所以我认为这个算法的整个顺序是O (n) 但我不确定

谁能帮我完整证明一下？

Answer 1

你是对的。

n减少的总次数不能超过原值（i和j永远不会是负数）

由于内部循环的每次迭代 n 正好减少一次，这为您提供了运行次数的上限，使您的代码 O(n).

你也可以看到这是一个紧边界，因为内循环第一次运行时，它将在 i >= n 时停止，这将在 ~n/2 迭代后发生，给出下限Omega(n) 还有。

Answer 2

如果你只想要大 O 或大 Theta 的时间复杂度，那么只计算上限和下限，这是更简单的情况。

考虑一下inner for loop，n到时候会减少一半，或者n每次走出inner for loop都会变成n/2（你已经知道了，因为j当时增加1个单位，n当时减少1个单位，所以j和n会在middle n 或 n/2）。当我们不知道代码何时停止时，事情会变得复杂，n = ?，但我们知道 n > 1

考虑下面的代码（上限）：

int x =0;

      for (;n > 1;) {

        for (int j = 1; j < n; ++j) {
            x++;
            n--;
        }
    }

n 将变为 n/2 每次迭代直到 n = 1，因此上面代码的复杂度将为 n/2 + n/4 + n/8 + ... + 1 = O(n).

下限更简单，假设 inner for loop 只运行 1 次迭代并且代码完成，1 次迭代给我们 n/2 运算符。所以下限是 O(n).

=> 总体复杂度为 O(n)。

我认为 upper - lower bound 方法的关键是在代码中省略一些 complex - hard to calculate - unclear changing variable 并将其与原始代码进行比较

如何计算这段代码的时间复杂度？

How to calculate the time complexity of this code?

algorithm

big-o

time-complexity