这个嵌套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

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