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

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

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

• i=0；j=0；最内层执行：0次
• i=1；j=0,1；最内层执行：1次
• i=2；j=0,1,2；最内层执行：2次
• i=3；j=0,1,2,3；最内层执行：3次
• i=n；j=0，1，2。。。，N最内层执行：n次

（对于j-loop，终止条件用粗体突出显示。当j-loop到达它时，最里面的表达式将不会被执行，我们将开始i-loop的下一次（如果有）迭代。）

因此，我们将有13。。。n。这是1/2（n*（n1）），这是n^2。因此，时间复杂度仍然是n^2。