N+ n-1 + n-2 + n-3 + (...) +1的大O复杂度

Question

我想知道..从n个元素开始的算法的复杂度是多少(我一直在做任何事情)。我去掉一个元素，再做一次..我去掉另一个元素，然后再做一次，直到我只剩下一个元素。是O(n log n)吗？我无法想象..。

Answer 1

据说著名的数学家Gauss在他上小学的时候就已经找到了解决这个问题的公式。正如@Henry在评论中提到的那样：

​

来源：Wikipedia (DE)，Wikipedia (EN)

因为每个条目都做了工作，即每个“项”都需要O(1)。因此，问题在O(n^2)中。

可视化(也称为Wikipedia)可以看作是一个半满的正方形：

​

Answer 2

为了解决O(n+n-1+n-2...n次)的复杂性，我们需要用see this link对数学公式求和

=> n+n+n...n times - (1+2+3...n times)
=> n^2- (n^2+n)/2

复杂度将为

(n^2-n)/2