求解运行时间大Theta符号

Question

考虑在这两个循环中找出总运行时间作为n的函数:

(1)

q  <- 1
while q <= n
p  <- 1
while p <= q 
p <- p + 1
q  <-  2 * q 
(2)
q,s <- 1, 1
while s < n
for j <- 1 to s        
k  <- 1
while k < = j  
k  <- 2 * k        
q  <- q + 1
s  <- q * q  

我知道我相信什么:(1) istheta(n * lg(n))其中n表示内循环的时间，而外环是Lg (n)(2)θ(n * lg (n) * sqrt (n))其中n表示for循环的时间，Sqrt (n)用于外部循环，lg(n)用于内部while循环。

我不确定这是否正确。如有任何建议，不胜感激。

Answer 1

(1):

这不是正确的看待这个的方式，事实上，内部的while-loop并没有做到"n循环lg n时间，则q无论这个数字是多少，每次迭代都要循环!

正确的分析方法是说内部while-loop运行q次，q取数字1, 2, 4, ... , n(是的，外部while-loop运行Θ(lg n)次)。

则整个运行时间为:

1 + 2 + 4 + ... + L注意，如果n不是2的完美幂，它的最大幂将小于n。因此，我们可以说它运行直到到达n(L = Θ(n))

计算得到一个几何级数lg(n)元素:

1 + 2 + 4 + ... + n = Θ(n)

(2):

不是一个最终的解决方案，但一个提示/启动你的分析仍然是错误的，说for-loop运行~n次，这个循环只是运行s次，s随着每次迭代而变化。在迭代t上，我们有s = t^2。

分析如下:for-loop和它内部的while-loop是相关的，j从1-s运行，while循环运行lg(j)——它们是相关的，因为j在for-loop的每次迭代中都发生了变化。但是我们需要记住s也在变化，所以for-loop运行s ∈ {1, 4, 9, ..., n}