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

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）时间（n的对数底数i + 1）。假设n为2的幂，并使用基本公式的更改转换为以2为基数：log_ {i + 1）（n）= lg（n）/ lg（i + 1），这意味着“某些代码”将执行多次：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））。

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