这个算法的时间复杂度是多少？这有点棘手

Question

假设我们有三重 for 循环，但是，其中的 O(1) 语句独立于第一个循环，例如：

for (int i=1; i<=n; i++)
{
   for ( int j=1; j<=20; j++)
   {
       for (int k=1; k<=5; k++)
               {
                     //some statements independent of n 
               }
    }
}

由于语句在最内层的 for 循环中独立于 n，所以它不是 O(n^2) 而不是 O(n^3) 吗？谢谢！

Answer 1

它是 O(n)，可能有一个更大的常数。两个内循环是固定的，与n无关。

Answer 2

请注意，内部循环 不依赖于 n:

for ( int j=1; j<=20; j++) 
   {
       for (int k=1; k<=5; k++)
               {
                     //some statements independent of n 
               }
    }

这就是为什么您可以将初始问题重写为

for (int i=1; i<=n; i++) {
   //some statements independent of n 
}

你有 O(n) 复杂性

Answer 3

复杂度为 O(n)。只有一个循环依赖于 n。考虑将 n 设置为非常高的数字。与其他循环相比，它并不是很有趣。

Answer 4

基本上你的代码运行的总迭代次数是=N*20*5，基本上等于运行N次迭代，所以你的时间复杂度是O(N)。

这个算法的时间复杂度是多少？这有点棘手

What is the time complexity of this algorithm? It is a bit tricky

algorithm

asymptotic-complexity