math - 以下方程的空间复杂度

Question

我无法弄清楚。我的一个程序的空间复杂度。它的出现如下，但我不确定它是 O(n ^3) 还是 O(n^4)

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

我认为1+ 2 + 3 + ....+ n = n*(n-1)/2

在这里我们有两个，所以我想知道它是否会是 O(n^4)

Answer 1

它是 O(n ³ )。

我已经计算了这个序列的前五个元素：

n=1 -> 1
n=2 -> 4
n=3 -> 10
n=4 -> 20
n=5 -> 35

整数序列在线百科全书® (OEIS®) 说这些是四面体（或三角锥体）数：a(n) = C(n+2,3) = n*(n+1)*(n+2)/6.

当然，这不是证据。您应该通过归纳检查您的总和是否满足这种关系。