时间循环迭代的大O值

Question

给出以下程序的大O值

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

通过绘制一个快速表，将I的值与每次迭代进行比较，我们可以看到：

如果n=5需要6次迭代

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

所以我说：

我们需要多少次迭代，直到2^k >n(其中k是迭代次数)

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

原木的底座是2。

但我现在卡住了..。我怎么才能从这得到大人物呢？

Answer 1

好吧，你已经有了答案。K告诉您最多需要多少次迭代。当您使用n，使用log(n)迭代时，您将结束循环。因此，该算法的渐近运行时间为O(log )。对数的基数并不重要，因为它只是一个常数:例如，ln = log(n)/log(e)。无论如何，在Big-O下您不会看到这个因素(在本例中是log)。