以下等式的空間複雜度

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

The On-Line Encyclopedia of Integer Sequences® (OEIS®) 說，這些是四面體（或三角錐型）編號：a(n) = C(n+2,3) = n*(n+1)*(n+2)/6。

當然，這不是一個證明。你應該檢查induction你的總和是否滿足這個關係。