我正在计算以下 Python 代码的运行时间复杂度，n^2但它似乎不正确。显示的正确答案是n(n-1)/2。谁能帮助我理解为什么内部循环不是运行n*n时间而是运行时间n(n-1)/2？
for i in range(n):
for j in range(i):
val += 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，这个问题很可能会询问确切的迭代次数（而不是渐近界）。
* 请参阅此处以获取此封闭表格的证明。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句