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

Question

这个问题是为了修改过去的试卷，如果我走上了正确的道路，我需要一些建议。

求出下面一段代码的时间复杂度T（n），表示给定整数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

几天前，有一个类似的问题，我提供了复杂性分析的逐步描述：https://stackoverflow.com/a/49093954/926701

• 外环确实是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））