时间戳

首页 > 解决方案 > 具有时间复杂度 log(log n) 的嵌套循环

time-complexity - 具有时间复杂度 log(log n) 的嵌套循环

问题描述

是否存在具有两个循环（嵌套）的算法，使得整体时间复杂度为 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)) 的类似循环？

标签： time-complexitycomplexity-theory

解决方案

对于迭代 O(log log n ) 次的循环，其中循环索引变量计数到n，那么索引变量必须像 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++) {
        // ...
    }
}

推荐阅读