以下是什么时间的复杂性？

Question

我已经看过很多这种类型的问题,但我仍然无法明确迭代.

for i=1...n
 for j=1..i
  k=n
  while (k>2)
   k=k^(1/3)

Answer 1

两个for循环O(n^2)组合在一起,内循环是O(log2(log2(n))[*].因此整体复杂性是O(n^2*log2(log2(n))).

要查找m内循环的迭代次数,我们需要解决以下问题m:

n = 2^(3^m)

这给出log3(log2(n))了O(log2(log2(n))(与使用相同的日志基础以保持一致性)相同.

[*]假设在你的符号中,k^(1/3)是立方根k.