嵌套循环的时间复杂度取决于外循环

Question

这是一个具有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)

有任何想法吗？

Answer 1

让我们计算最里面的表达式执行的次数，所以我们这样说：

• 我 = 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。