嵌套循环的时间复杂度取决于外循环
这是一个具有n^2复杂性的普通嵌套循环
for i in range(n):
for j in range(n): # <-- dependent on n
print(i,j)
我很难理解为什么下一个循环n^2即使打印较少的语句也具有复杂性
for i in range(n):
for j in range(i): # <-- now it is dependent on i
print(i,j)
有任何想法吗？
回答
让我们计算最里面的表达式执行的次数，所以我们这样说：
- 我 = 0; j = 0 ; 最里面执行：0次
- 我 = 1; j = 0, 1 ; 最里面执行：1次
- 我 = 2; j = 0, 1, 2 ; 最里面执行：2次
- 我 = 3; j = 0, 1, 2, 3 ; 最里面执行：3次
- ...
- 我 = n; j = 0, 1, 2, ..., n ; 最里面执行：n次
（对于 j-loop，终止条件用粗体突出显示。当 j-loop 到达它时，最里面的表达式将不会被执行，我们开始下一次（如果有）i-loop 迭代。）
因此，我们将有1+2+3+...+n. 哪个是1/2(n*(n+1))，哪个是n^2。因此，时间复杂度仍然是 n^2。