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

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中编写了这段代码，并在循环结束后打印了x的最终结果，对于不同的n值，我看到跳入内部for循环需要将近n倍的时间。

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

Answer 1

如果你只想要大O或大θ的时间复杂度，让我们只计算上界和下界，这是更容易的情况。

考虑inner for循环，n将在时间上减少一半，或者n将在每次离开inner for循环时变为n/2（您已经知道，因为j在时间上增加1个单位，n在时间上减少1个单位，所以j和n将在中间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，因此obove代码的复杂性将是n/2+n/4+n/8+...+1=O(n)。

下限甚至更容易，假设内部for循环只运行1次迭代，代码完成，1次迭代给出N/2运算符。所以下限是O(n)。