c++ - 2个对数嵌套for循环的Theta运行时间

Question

什么 Theta 运行时有以下代码？

void f(int n)
{
  for(int i=1; i<n; i*=5)
    for(int j=n; j>0; j/=2);
}

我想出了这个： T(n) = log(n) * (1 + log(n)) = log(n) + log^2(n) 现在我不知道在 Theta 符号中输入什么?

Answer 1

log(n) + log^2(n) = Theta(log^2(n))。你只需要采用主导词。要看到这个，你可以写

log^2(n) <= log(n) + log^2(n) <= 2*log^2(n)

这足以证明 T(n) 是 Theta(log^2(n))。