确定内环具有外环对数频率时的时间复杂度

Question

我是分析时间复杂性的新手。有人能帮我解决以下算法的时间复杂度吗？

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

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

     i=i*2;
   }
}

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

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

Answer 1

外部循环将运行（对数n）次。

由于内部循环是由i绑定的，所以它将为log1 log2 log3运行。。。不同i值的对数（n-1）次。解决上述问题可推断为

=对数（1*2*3…（n-l）。（因为loga*logb=loga*b）

=对数（（n-1）！）。（这是（n-1）阶乘）

=（n-1）log（n-1）.（

所以内环的复杂性为O（nlogn）。

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

洛恩洛恩

即O（nlogn）。

Answer 2

给定函数的时间复杂度为O（log n log n）=O（log^2 n）。

外环具有时间复杂度O（log n）。同样，内环也具有时间复杂度O（log n），因为i的值以n为界。因此log i=O（log n）。