在第一次运行内部循环时
i = 0
这个
for
循环根本不执行。(在中有零个元素需要迭代。)
range(0)
).
在第二次运行内部循环时
i = 1
这个
对于
循环执行一次迭代。(其中有一个元素需要迭代。)
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
,问题很可能是询问迭代的确切次数(而不是渐近界)。
