algorithm - 大哦嵌套而

Question

我遇到了一些大 O 问题的挑战。这些不是家庭作业问题。我写这些问题是为了更好地理解这里的概念。

function func(n)
{
     int k,i = 0;
     while(k < n){ < --- Guessing this outer loop is O(n/2)
        k = n + 2
        i = 0;
        while(i < k){ <--- Not sure what this is?
            i ++;
            i = i * i;
         }
      }         
}

如果你能向我解释内部循环中发生了什么，以及你的逻辑如何以你最终结束的 big-o 符号结束，我真的很高兴。

Answer 1

外循环及其测试 (k < n)及其步骤，k = n + 2 , 将运行一次，复杂度为 O(1)。

内循环有测试(i < k)也就是说(i < n+2) , 并且有步骤 i++; i=i*i;最后，

i = (...(((1+1)^2+1)^2+1)^2+ ... )^2 > n+2` 

这使得 i 的值超指数。即 i在 p 遍中比 exp(exp(p)) 增长得更快，因此总体复杂度小于 O(log log n)。这是一个比前面提到的 O(log n) 更严格的界限，后者也是一个上限，但没有那么严格。