Source-Theta 分析算法

Question

我正在做一些介绍性的算法分析练习题，并且在某些方面仍然有些不稳定。我尝试了下面的练习，但没有答案。评论是我自己的工作。我想知道是否有任何在这方面有经验的人愿意看看我的尝试，并让我知道我是否已经正确地接近它。感谢您的帮助！

"Give the asymptotic worst case running time of the following pseudocode as a Big-Theta expression."

 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)+nO(log n)+2nO(log n)+2+1 =

//5+(3n+1)*O(log n) =

//ϴ[(3n+1)log n]

Answer 1

总的来说，方法和最终结果都不错，但有一些小方面可以更正：

因为您对 Big-Theta class 感兴趣，所以最好从一开始就使用它。这将阻止从 Big-O 到 Big-Theta 的最终转换，即执行 5+(3n+1)*O(log n) = ϴ[(3n+1) 的步骤log n])，这在一般情况下是不正确的。
k ← k/2 //1 for division + 1 for assignment在while k ≥ 1 do //O(log n)循环中，因此在考虑总复杂度时应该乘以log(n)。尽管如此，最终的结果仍然是正确的，因为复杂度是由最内层循环所做的工作决定的。

Source-Theta 分析算法

Big-Theta Algorithm Analysis

algorithm

asymptotic-complexity

big-theta