为什么这个算法复杂度为 O(n^2)？

Question

我知道这个算法的大O复杂度是O(n^2)，但我不明白为什么。

int b=0;
for(int i=n; i>0; i--)
   for(int j=0; j<i; j++)
      b=b+5;

我知道外层循环是O(n)。我知道内循环将 运行 n + (n-1) + (n-2) + ... + 1 次。这是我所能得到的。我不确定从那里去哪里。

My question is, can somebody explain why that algorithm is O(n^2) ?

Answer 1

因此，整个代码块的总次数 运行

= n + (n-1) + ...+ 1 
= n * (n+1) / 2 
= O(n^2).

其他语句将采用 O(1)，因此它们对复杂性（它们是常数）没有影响（作用不大）。

Answer 2

基本上是因为比单次循环多了n^2次操作。

Answer 3

外循环 |内循环
i=n |内循环执行n次
i=n-1 |内循环执行n-1次
i=n-2 |内循环执行n-2次
.
.
.
i=1 |内循环执行1次并退出

现在总结内循环执行的总次数：n + (n-1) +(n-2)+.....+1= n*(n+1)/2 = O(n²)