algorithm - While循环时间复杂度

Question

我有一个算法考试..在循环时间复杂度方面有点不太好：我刚刚开始了解它的基础知识..

我有这个while循环

i=2
while (i<n)
{
   i=i*i
   x=x+1
}

我相信解决方案必须是这样的： （i） 每次执行语句 1 次时
将从 2 运行到 2 ^k，其中 k = 2 ^{i ..}

所以 1+1+1+.. ，这意味着 1*2 ^k

从这里我无法继续..

第二个问题伙计们..请推荐一个我可以练习更多这些的网站或某事..搜索但没有找到：s

Answer 1

只要i小于，循环就会运行n。换句话说，你需要找到k2 ^{2 k} < n。==> k = log ₂ log ₂ n。所以循环迭代 log ₂ log ₂ n 次，并且在每次迭代中它执行 2 个操作（乘法和加法） - 这些操作需要O(1)时间。

==> 执行循环的时间等于 log ₂ log ₂ n * O(1) ==> 总复杂度为O(loglogn).