嵌套for循环的运行时复杂性，但内部循环只能达到外部的当前索引

Question

for i in range(n):
   for j in range(i):
      print j

尽管内部循环只能达到外循环当前索引的长度，但我还能声称这是O（n ^ 2）吗？

Answer 1

计数到n的循环描述了一条线，一个嵌套的循环都计入n描述了一个正方形。

当内循环上升到外循环的索引时，您将覆盖三角形的一半正方形：

+----+
|.   |
|..  |
|... |
|....|
+----+

这样您就可以通过计算三角形的面积来更准确地预测运行时间。但是Big-O表示法并不是要获得精确的运行时，而是要比较运行时在添加更多数据时如何扩展。你想知道你的程序最接近哪个of these lines。三角形的大小仍然与n*n成比例增加。覆盖正方形的一半并不足以使程序更接近不同的复杂性类别。