n + n-1 + n-2 + n-3 +(...)+ 1的Big-O复杂度 [英] Big-O complexity for n + n-1 + n-2 + n-3 + (...) + 1

问题描述

我想知道..从n个元素开始的算法的复杂性是什么(我会做任何事情).我取下一个元素，然后再次执行..我取下另一个元素，然后再次执行，直到只剩下一个元素. 是O(n log n)吗?我无法想象...

I was wondering.. what is the complexity of an algorithm that starts with n elements (which I run through doing whatever). I take one element off, I do it again.. I take off another element and do it again until I have just one element left. is it O(n log n)? I can't visualize it...

推荐答案

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

The famous mathematician Gauss is said to have found a formula for that exact problem when he was in primary school. And as mentioned by @Henry in the comments it is:

来源:维基百科

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

As work is done for every entry, i.e., O(1) is required for each "item". Hence, the problem is in O(n^2).

可视化效果(也 Wikipedia )可以看作是半填充的正方形:

Visualisation (also Wikipedia) can be seen as a half filled square:

这篇关于n + n-1 + n-2 + n-3 +(...)+ 1的Big-O复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！