问大O，对一系列n个数字求和的复杂度是多少？

EN

这并不是问题的复杂性，而是算法的复杂性。

在您的例子中，如果您选择遍历所有的数字，那么复杂度实际上是O(n)。

但这不是最有效的算法。一种更有效的方法是应用公式- n*(n+1)/2，它是常量，因此复杂度是O(1)。

它等同于BigO (n^2 )，因为它等同于(n^2+ n) / 2，并且在BigO中您忽略了常量，所以即使n的平方除以2，您仍然可以按平方的速率进行指数增长。

想想O(n)和O(n/2)？我们同样不区分这两者，对于较小的n，O(n/2)只是O(n)，但增长率仍然是线性的。

这意味着随着n的增加，如果你要在图上绘制操作的数量，你会看到一条n^2曲线出现。

你可以看到这一点：

when n = 2 you get 3
when n = 3 you get 6
when n = 4 you get 10
when n = 5 you get 15
when n = 6 you get 21

如果你像我在这里做的那样绘制它：

​

​

你会看到这条曲线类似于n^2，你在每个y处都会有一个更小的数字，但这条曲线与之相似。因此，我们说大小是相同的，因为随着n的增大，它的时间复杂度将类似于n^2的增长。

用两种方法可以求出n个自然数的级数和的解。第一种方法是将循环中的所有数字相加。在这种情况下，算法是线性的，代码将如下所示

 int sum = 0;
     for (int i = 1; i <= n; i++) {
     sum += n;
   }
 return sum;

它类似于1+2+3+4+......+n，在这种情况下，算法的复杂度计算为执行加法运算的次数，即O(n)。

求n个自然数级数和的第二种方法是最直接的公式n*(n+1)/2，该公式用乘法代替重复加法。乘法运算不具有线性时间复杂度。有各种算法可用于乘法，其时间复杂度从O(N^1.45)到O (N^2)不等。因此，在乘法的情况下，时间复杂度取决于处理器的体系结构。但出于分析的目的，乘法的时间复杂度被认为是O(N^2)。因此，当使用第二种方法求和时，时间复杂度将为O(N^2)。

这里的乘法运算与加法运算不同。如果任何人有计算机组织学科的知识，那么他就可以很容易地理解乘法和加法运算的内部工作原理。乘法电路比加法电路更复杂，并且需要比加法电路高得多的时间来计算结果。因此级数和的时间复杂度不可能是常数。