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

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

如果你只想要大 O 或大 Theta 的时间复杂度，让我们计算上界和下界，这是更容易的情况。
考虑 inner for loop , n此时会减少一半，或者n会变成n/2每次出门都是inner for loop (你已经知道对了，因为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在代码中并将其与原始代码进行比较