时间戳

首页 > 解决方案 > 如何确定以下代码的时间复杂度

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

问题描述

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) 次的外循环。我们如何计算内部循环将执行的次数？上述代码的时间复杂度是多少？

标签： algorithmtime-complexitybig-ocomplexity-theory

解决方案

内部循环需要 log_{i+1}(n) 时间（log base i+1 of n）。假设 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))。

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

推荐阅读