我不明白在这两种情况下如何计算时间复杂度

Question

这是第一个算法。它没有任何正确的语法：

for(i=1;i<=n;i++)
  {for(j=1;j<=i;j++)
       for(k=1;k<=100;k++)
        {printf("hello")
         }
        }
      }

在这种情况下，我们通过查看 printf 语句将执行的总次数来计算时间复杂度为 O(n^2(。因此，我们将 k 循环为每个 i 从 1 到 n 运行的次数相加。

第二个代码：

{int n=(2)^(2)^k //read as 2 to the power 2 to the power k
 for (i=1;i<=n;i++)
 {j=2
  while(j<=n)
  {j=j^2
   printf("hello")
  }
 }
}

这里我们得到的时间复杂度为 O(n(loglogn((。我们看到第 n 个循环将执行 n(k+1( 次。我们替换了k的值并得到了时间复杂度。

我不明白为什么我们没有像在第一个代码中那样添加 print 语句执行的总次数来计算第二个代码中的时间复杂度。我们只看到它在第 n 次循环中运行了多少次来计算答案。

Answer 1

你需要清除你的基础知识。第一个循环的时间复杂度是O(N^2(，它与printf语句完全无关。它大约是你最内层循环的迭代总数。

code 1中最里面的循环运行100*(N^2)即 O(N^2(，即使代码 1 为：

for(i=1;i<=n;i++)
  {for(j=1;j<=i;j++)
       for(k=1;k<=100;k++)
        {
         }
        }
      }

因此，只要您的最内层循环没有语句或需要 O(1( 时间的语句，答案就保持不变。

对于你的第二个代码：while 循环总是运行 log(logn) 次，而外部循环总是运行 n 次，因此时间复杂度为 O(nlog(logn((，因为这是最内层(while(循环的迭代总数。