用log进行算法运行时间分析

Question

我在这里有以下算法伪代码：

for (j = 2 to n){
 k=1
 while (k<j^2) {
  k=2*k
 }
}

我学到的方法只是逐行分析，所以第1行我可以看到它运行n-2次，而第2行符文n-1次。

让我困惑的是while循环，我不太清楚如何处理它。我认为它自己运行log（j2）次，所以我得到类似（n-1）* log（j2）的第3行？但是我们不应该拥有n方面的所有东西吗？

Answer 1

内部while循环isTheta(log j^2) = Theta(2 log j) = Theta(log j)。

所以总运行时间是Theta(2(log 2 + log 3 + ... + log n)) = Theta(n log n)

Answer 2

您可以使用Sigma表示法。

以下参考如何将对数与sigma组合：