嵌套循环的时间复杂度依赖于外层循环

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.