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

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，2n；最内层执行：n次

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

因此，我们将有1+2+3+...+n。即1/2(n*(n+1))，即n^2。因此，时间复杂性仍然是n^2。