algorithm - 这个嵌套 for 循环的运行时间是多少？

Question

for i = 1 to n   
  for j = 1 to i - 1

这是 O(n^2) 的运行时间吗？在处理这些类型的问题以找到正确答案时，是否有一种很好的方法来可视化事物？

Answer 1

内循环执行

1 + 2 + 3 + 4 + 5 +...n-1 = n*(n-1)/2 times

使用算术级数和的公式，所以整体复杂性是 O(n^2)

Answer 2

每个for循环为O(n)，两个for循环为O(n)*O(n) = O(n^2)

检查此链接。作者解释了计算运行时的好方法。