如何找到一系列算法的时间复杂度？

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).

内部循环是运行

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

另一方面，

Space complexity 在这种情况下更简单。由于内存要求不依赖于输入长度，space 上述算法的复杂度为 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)

这反过来导致[=19=]

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)，如接受的答案中所述。

How to find the time complexity of a algorithm of a series ?