algorithm - 为什么这个算法复杂度为 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)，因此它们对复杂性(它们是常数)没有影响(作用不大)。