两个嵌套 for 循环的时间复杂度

Question

这道题是从过去的试卷中修改而来的，如果我走对了路，需要一些建议。

根据给定的操作数integer n计算出以下代码段的时间复杂度T(n)：

for ( int k = n; k >0; k /= 3 ) {
  for ( int i = 0; i < n; i += 2 ) {
     // constant number C of elementary operations
  }
  for ( int j = 2; j < n; j = (j*j)) {
      // constant number C of elementary operations
  }
}

所以我认为外循环是O(logn)，第一个内循环是O(n)，第二个内循环是O(logn)。只是想知道我是否有一个粗略的想法以及如何从这里前进。

Answer 1

前几天有个类似的问题，我提供了step-by-step复杂性分析的描述：

外循环确实是O(log3(n))
第一个内循环确实是O(n)
第二个内循环是O(log2(log2(n)))

非正式地，对于第二个循环，j(k) for 循环的索引 j 所取值的序列，我们可以写成：

j(1) = 2, j(2) = j(1)^2 = 4, j(3) = j(2)^2 = 16, ..., j(k) = j(k-1)^2 >= n 
=> j(k) = j(k-1)^2 = j(k-2)^4 = ... = j(1)^(2^k) = 2^(2^k)
=> k = log2(log2(n))

由于内循环的操作数与外循环的操作数独立，我们可以乘以复杂度：

T(n) = O(log3(n) * (n + log2(log2(n))))
     = O(n.log3(n))

因为 log2(log2(n)) << n 作为 n -> +Inf.

两个嵌套 for 循环的时间复杂度

Time complexity for two nested for loops

time

complexity-theory

time-complexity