Big-Theta算法分析

Question

我正在做一些介紹性的算法分析實踐問題，在它的某些方面仍然有點不穩定。我已經對下面的練習拍了一下，但沒有答案。評論是我自己的工作。我想知道在這方面有經驗的人是否願意看看我的嘗試，並讓我知道我是否正確接近它。任何幫助表示讚賞！

---

「將下面的僞代碼的漸近最差情況運行時間作爲Big-Theta表達式。」

procedure Sum(n) 
    S ← 0 //1 for assignment 
    k ← n //1 for assignment 
    while k ≥ 1 do //O(log n) 
     for i = 1, 2, . . . , n do //n*O(log n) 
      S ← S + n //(1 for assignment + 1 for addition)*n*O(log n) 
     end for 
     k ← k/2 //1 for division + 1 for assignment 
    end while 
    return S //1 for return 
end procedure 

//合計爲1 + 1 + O（log n）的+ N O（log n）的+ 2N O（log n）的+ 2 + 1 =

// 5 +（ 3N + 1）* O（log n）的=

//Θ[（3N + 1）日誌n]的

Answer 1

總體而言，該方法是很好的，以及作爲最終結果，但也有一些小的可以糾正的方面：

• 因爲您對Big-Theta類感興趣，所以最好從頭開始使用它。這會阻止從Big-O到Big-Theta的最終轉換，即，執行5+（3n + 1）* O（log n）=Θ[（3n + 1）log n]的步驟，這不是一般來說是真的。

• k ← k/2 //1 for division + 1 for assignment位於​​循環內部，因此在考慮整體複雜度時應該乘以log（n）。儘管如此，最終的結果仍然是正確的，因爲複雜性主要取決於在最內層循環中完成的工作。