确定内循环运行两次外循环变量时的时间复杂度

Question

我是分析时间的新手complexity.some有人能帮我解决下面算法的时间复杂度吗？

public void test(int n)
{
  int i=1;

   while(i<n)
   {
      int j=0; 
      while (j<n)
      {
         j=j+(2*i);
      }

     i=i*2;
   }
}

外部循环将运行日志（n）次。内部循环将运行多少次。我们如何用“n”来计算内环的频率，因为它取决于变量“i”。

有人能帮忙找出上面代码的时间复杂度吗。

Answer 1

外循环将运行log（n）次。

说n=32。因此，内部循环将运行：

• n/2对于i=1

所以这个几何级数的和是

即n/2 n/4 ..... 1

因此，上述算法的时间复杂度是

logn + 2n

这是O（n）。