时间复杂度为 log(log n) 的嵌套循环

Question

能否有一个算法有两个循环（嵌套），使得总时间复杂度为 O(log(log n))

这是在解决以下问题后出现的：

for(i=N; i>0; i=i/2){
  for(j=0; j<i; j++){
    print "hello world"
  }
}

以上代码的时间复杂度为N。（使用几何级数的概念）。是否存在时间复杂度为 O(log(log n)) 的类似循环？

Answer 1

对于循环迭代O(log log n)次，其中循环索引变量计数到n，则index 变量必须像 log log k 的反函数一样增长，其中 k 是迭代次数；即它必须像 2^2^k 或 2.

以外的其他基数增长

实现此目的的一种方法是从 2 开始并重复平方直到达到 n - 如果索引变量是 (((2^2)^2).. .^2) 使用 k 平方，则根据需要等于 2^2^k：

for(int i = 2; i < n; i = i*i) {
    //...
}

这个循环根据需要迭代O(log log n)次。如果你绝对必须用嵌套循环来做，我们可以简单地添加一个额外的循环，迭代 O(1) 次，使迭代总数渐近相同：

for(int i = 2; i < n; i = i*i) {
    for(int j = 0; j < 10; j++) {
        // ...
    }
}

Nested loops with time complexity log(log n)