algorithm - 这个特定算法的时间复杂度

Question

如果我要问的问题很明显，请原谅我，但我已经考虑了 2 个小时了!我就是想不通....

嗯，我有类似的东西:

for(int i=0;i<N;i++)
  for(int j=0;j<i;j++)

我当然可以说复杂度是 O(N+(N-1)+(N-2)...)，但是这种类型有更简单的表示法吗？

谢谢

Answer 1

注意:

第一次交互:1次执行命令行

第二次交互:命令行的 2 次执行

...

第N次交​​互:N次执行命令行

= sum 1 + ... N= 等差数列和=(N/2)(1+N)

因此，O(N^2)。