循环时间复杂度O(logn)

Question

我无法理解为什么这段代码的时间复杂度为O(logn):

double n;
/* ... */
while (n>1) {
     n*=0.999;
}

至少它在我的学习资料中这么说.

Answer 1

想象一下,如果代码如下:

double n;
/* ... */
while (n>1) {
     n*=0.5;
}

我希望,直观地看到这是O(logn).

当你乘以0.999时,它会因常数因子而变慢,但当然复杂性仍然写为O(logn)

Answer 2

您想要计算之前需要的迭代次数n等于(或小于)1.

如果您调用k要解决的迭代次数

n*0.999 ^ k = 1

它是这样的

n*0.999 ^ k = 1

0.999 ^ k = 1/n

log(0.999 ^ k)= log(1/n)

k*log(0.999)= -log(n)

k = -log(n)/ log(0.999)

k =( - 1/log(0.999))*log(n)

对于big-O我们只关心"大局",所以我们抛弃常数.这log(0.999)是一个负常数所以(-1/log(0.999))是一个正常数,我们可以"扔掉",即设置为1.所以我们得到:

k~log(n)

所以代码是O(logn)

由此您还可以注意到,常量的值(即示例中的0.999)对于big-O计算无关紧要.所有大于0且小于1的常量值将导致O(logn).