依賴循環的複雜性

Question

2我開發了一種算法，我試圖以最詳細的方式記錄它的時間複雜性，並且我遇到了一個問題。

的算法是這樣的：

for i=0:n { 
    task 1; 
    task 2; 
    for j=0:i { 
     task 3; 
    } 
    task 4; 
} 

所以我記錄我的複雜性說，任務1具有複雜度O（T1），... 但是當我試圖解釋的任務3我被卡住了，因爲它基本上會被執行，我計劃說算法的複雜性是任務1 +任務2 +任務3 +任務4的複雜度的n倍。而且，我將依賴於n我真的不明白什麼是最好的呈現方式。

我明白，如果任務1,2和4不存在，複雜度將是O（n^2）。但我不知道如何與我以前的解釋一致來呈現。

我希望有道理，謝謝你的幫助。

Answer 1

最簡單的方法可能是將它們分開計數。

執行任務3：1+2+3+...+n = n(n+1)/2次。

任務1,2和4每個執行n次。

左右（假設每個任務需要O(1)）我們擁有的

O(n(n+1)/2 + 3n) = O(n²/2 + n/2 + 3n) = O(n²) 

複雜性（持續性因素和漸近小的方面可以在大O符號被忽略）。

---

更普遍的（如果每個任務並不一定需要O(1)），我們可以說其複雜性：

O(t3*n² + n*(t1 + t2 + t4)) 

其中ti代表i任務需要多長時間。