如何确定以下代码的时间复杂度

Question

public void test(int n)
{
   for(i=1;i<=n;i=i*2)
  {
     for(j=1;j<n;j=j+(j*i))
      {
         // some code
      }
  }
}

以上代码有两个循环。执行 log(n) 次的外循环。我们如何计算内循环将执行的次数？以上代码的时间复杂度是多少？

Answer 1

内部循环需要 log_{i+1}(n) 时间（log base i+1 of n）。假设n是2的幂，利用换底公式，换算成以2为底：log_{i+1)(n) = lg(n)/lg(i+1)，即"some code" 将被执行多次：lg(n)/lg(2) + lg(n)/lg(3) + lg(n)/lg(5) + ... + lg(n)/lg( n+1).

现在，1/lg(2) + 1/lg(3) + ... + 1/lg(n+1) <= 1 + 1/lg(2) + 1/lg(4) + ...1/lg(n) = 1 + 1/1 + 1/2 + 1/3 + ... + 1/lg(n) ~= (1 + log(lg(n))).

类似地，1/lg(2) + 1/lg(3) + ... + 1/lg(n+1) >= 1/lg(4) + 1/lg(8) + 。 .. + 1/lg(2n) ~= (log(lg(2n)) - 1)。（使用谐波数的近似值：H(n) ~= log(n)）。

这样看来复杂度是log(n)log(log(n)).

这是一个非常粗略的证明，但希望能为您指明正确的方向。

如何确定以下代码的时间复杂度

How to determine time complexity of below code

algorithm

complexity-theory

big-o

time-complexity