大O問題 - 算法分析II

Question

我在做一個問題，要求找到使用大O表示法簡化的嵌套for循環的複雜性。

的問題是：

for i <- 1 to n do 
    for j <- 1 to n do 
     for k <- 1 to (i+j) do 
      a unit cost operation 

我必須證明上述使用一系列符號的總和。我有點理解這個概念，並給出了一個解決方案。我只想知道我是否正確地做了。

這是我的答案：

**假定總和（X = I，y）是與x作爲下限和y作爲上限資本西格瑪符號。和（i = 1，n）sum（j = 1，n）sum（k = 1，i + j）1
=中，n）（I + J）
=>總和（I = 1，N）N * I => N *總和（I = 1，N）1

在規則膠層爲等差級數的總和給出了： => N * N/2（N + 1） =>（N^3 + N^2）/ 2

使用大哦規則 - > MAX（F（X），G（X）） ： => max（n^3/2，n^2/2） => O（n^3）

我知道答案是正確的，但如果之前我的計算中是我不知道....

Answer 1

有了小幅盤整：

sum(i=1, n) sum(j=1, n) sum(k=1, i+j) 1 
= sum(i=1, n) sum(j=1, n) (i+j) 
= [ sum(i=1, n) sum(j=1, n) i ] + [ sum(i=1, n) sum(j=1, n) j ] 
= sum(i = 1, n) n*i   + sum(i=1, n) n*(n+1)/2 
= n * sum (i = 1, n) i  + n * n * (n+1)/2 
= n * n * (n+1)/2   + n * n * (n+1)/2 
= n * n * (n+1) 
= n^3 + n^2 
= O(max(n^3, n^2))   <--- as you correctly say 
= O(n^3) 

其實，這是Θ(n^3)

---

您也可以使用i+j <= 2*n：

sum(i=1, n) sum(j=1, n) sum(k=1, i+j) 1 
= sum(i=1, n) sum(j=1, n) (i+j) 
<= sum(i=1, n) sum(j=1, n) 2*n 
= 2*n * sum(i=1, n) sum(j=1, n) 1 
= 2 * n^3 
= O(n^3) 

Answer 2

直截了當和正式（和經驗證實），與c - >單位成本操作：