While循环时间复杂度 [英] While loop Time complexity

问题描述

我有一个算法考试..和我有点不是很大的循环时间复杂度：■我刚开始得到它的基本功能。

I have an algorithm exam.. and am a bit not great in the loops time complexity :s I just started to get the basics of it..

我有这个while循环

I have this while loop

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

我认为，解决办法必须是这样的：
（一）将运行2至2 ^K 其中k = 2 ^我
每次它执行语句1次。

I believe that the solution must be like:
(i) will run from 2 to 2^k where k = 2ⁱ
every time it execute the statement 1 time..

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

so 1+1+1+.. , this means 1*2^k

，从这里我无法继续。

第二个问题家伙..请推荐一个网站或者某事，我可以练习一些更多的这些..搜查，但没有发现：■

the second question guys.. please recommend a site or sth that I can practice some more of these.. searched but didn't find :s

推荐答案

环路只要我小于 N 。换句话说，你需要找到 K ，使得2 2 K ＆LT; ñ。 ==> K =日志 2 日志 2 ñ。因此，循环迭代日志 2 日志 2 n次，在每次迭代将执行2的操作（乘法和加法） - 这些行动采取 O（ 1）的时间。

The loop runs as long as the i is less than n. In other words, you need to find k such that 2^2k < n. ==> k = log₂log₂n. So the loop iterates for log₂log₂n times and at each iteration it performs 2 operations (multiplication and addition) - these operations take O(1) time.

==>执行循环的时间等于登录 ₂ 日志 ₂ N * O（1）==>总的复杂性是 O（loglogn）。

==> The time to execute the loop is equal to log₂log₂n * O(1) ==> total complexity is O(loglogn).

这篇关于While循环时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！