如何求出序列算法的时间复杂度？

Question

如何找到产生级数求和的下列算法的复杂性。

系列: 1+(1+2)+(1+2+3)+.......+(1+2+3+...+n)

算法：

 for(i=1; i<=n; i++){
       for(j=1; j<=i; j++){
           sum = sum + j;
       }
 }

Answer 1

要找到时间复杂度，让我们分析内核运行多少次(在循环中)。

外部循环运行n次，因此复杂度至少是( O(n) )。

内部循环正在运行。

• 一次当i=1
• 两次当i=2
• ..。N次时i=n

所以运行它的总次数是1到n之间的整数之和：(n * (n+1)) /2= n^2 /2+n/ 2，即O(n^2)。

另一方面，空间复杂性在这种情况下更简单。由于内存需求不取决于输入长度，上述算法的空间复杂度为O(1) (意味着所需的内存量(基本上与sum的大小)相同，而不考虑n，且结果是否符合sum)。

请注意，对于相同的任务，不同的算法可能有不同的复杂性。正如@AxelKemper在他的评论中正确指出的，您可以将解表示为n的单个多项式，因此最有效的解将具有O(1)的复杂性。然而，上述算法并不是这样工作的，而且具有较高的复杂度。

Answer 2

之和

1+(1+2)+(1+2+3)+.......+(1+2+3+...+n)

等于

1/2(1+1) + 2/2(2+1) +3/2(3+1)+.+n/2(n+1)

这可以重写为

1/2(1+2+...+n) + 1/2(1+4+9+....+n*n)

这反过来又导致

n/4(n+1) + 1/12(2n^3 + 3n^2 + n)

可以简化为

n^3/6 + n^2/2 + n/3

忽略n的字长，计算该多项式的复杂度不依赖于n。

因此，问题的时间复杂度是O(1) ()。

所示算法的时间复杂度为O(n^2)，如所接受的答案中所解释的那样。