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

Question

我在想..从n个元素开始的算法的复杂性是什么(我通过做任何事情来运行).我取下一个元素,我再做一次.我取下另一个元素再做一次,直到我只剩下一个元素.是O(n log n)？我无法想象它......

Answer 1

据说着名的数学家高斯在小学时就找到了这个确切问题的公式.正如@Henry在评论中提到的那样:

资料来源:维基百科

由于每个条目都要完成工作,即每个"项目"都需要O(1).因此,问题在于O(n ^ 2).

可视化(也称维基百科)可以看作是半满的方块: