algorithm - 我无法理解在这两种情况下如何计算时间复杂度

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的值，得到时间复杂度。

我不明白为什么我们不像在第一个代码中那样在第二个代码中添加打印语句执行的总次数来计算时间复杂度。我们只看到它在第 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)循环的总迭代次数。