两个嵌套for循环的运行时

Question

我将下面 Python 代码的运行时间复杂度计算为 n^2，但它似乎不正确。显示的正确答案是 n(n-1)/2。谁能帮助我理解为什么内部循环不是运行ning n*n 次而是 n(n-1)/2 次？

for i in range(n):
    for j in range(i):
        val += 1

Answer 1

在内循环的第一个运行上，当i = 0时，for循环根本不执行。（range(0) 中有零个元素要迭代）。

在内循环的第二个运行，当i = 1时，for循环执行一次迭代。（在 range(1) 中有一个元素要迭代）。

然后，第三个有两个元素运行，第四个有三个，按照这个模式，直到i = n - 1。

总迭代次数为0 + 1 + ... + (n - 1)。这个求和有一个众所周知的形式*：对于任何自然 m、0 + 1 + ... + m = m * (m + 1) / 2。在这种情况下，我们有 m = n - 1，因此总共有 n * (n - 1) / 2 次迭代。

你是对的，这个算法的渐近时间复杂度是O(n^2)。但是，鉴于您已经说过“正确答案”是 n * (n - 1) / 2，问题很可能会询问确切的迭代次数（而不是渐近界限）。

_{* 请参阅 here 以获得此封闭形式的证明。}

Runtime of two nested for loops