迭代SOF while循环大O值 [英] Big-O value for iteration sof a while loop

问题描述

举一个大O估计下面的程序

Give a big-O estimate for the following program

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

通过绘制一个快速的表，比较值的我的每次迭代，我们看到的是：

by drawing a quick table, comparing the value of i to each iteration we see that:

如果 N = 5 的，我们需要6次迭代

if n=5 we need 6 iterations

如果 N = 7 的，我们需要的8次迭代，等等...

if n=7 we need 8 iterations, and so on...

所以我说：

多少次迭代我们需要直到2 ^ K> n（其中k是迭代次数）

how many iterations do we need until 2^k > n (where k is the number of iterations)

 2^k > n
 log(2^k) > log(n)
 k > log(n)

其中，日志基地2。

where log is of base 2.

不过，我现在被困...我如何从这个得到大O？

But I am stuck now... how do I get the big-O from this?

推荐答案

那么，你有答案alraedy。第k告诉你，你有多少次迭代需要最多。当你把一个n，与log（n）的迭代，你会结束循环。因此，该算法的渐近运行时间为O（log n）的。 的对数的底数不要紧，因为它只是一个常数因子：例如LN N =的log（n）/日志（E）。你不会看到反正这个因素（在这种情况下，登录e）根据大澳。

Well, you have the answer alraedy. The k tells you how many iterations you need at most. When you take an n, with log(n) iterations you will end the loop. Thus, the asymptotic running time of the algorithm is O(log n). The base of the logarithm doesn't matter, because it is just a constant factor: e.g. ln n = log(n)/log(e). You won't see this factor (log e in this case) under Big-O anyway.

这篇关于迭代SOF while循环大O值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！