c - 计算复杂度英文 - 虽然循环时间复杂度O(logn)




算法复杂度总结 (2)

我不明白为什么这个代码的时间复杂度是O(logn)

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

至少在我的学习资料里是这样说的。


你想在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)

对于大O我们只关心“大局”,所以我们扔掉常量。 这里log(0.999)是一个负常数,所以(-1 / log(0.999))是一个正的常量,我们可以“扔掉”,即设置为1.所以我们得到:

k〜log(n)

所以代码是O(logn)

从这里你也可以注意到,常数的值(即你的例子中的0.999)对于大O计算并不重要。 所有大于0且小于1的常数值将导致O(logn)。


对数有两个输入:一个基数和一个数字。 对数的结果是你需要提高基数以达到给定数量的能力。 由于你的基数是0.999,这个数字是第一个小于1,你有一个标量,这是n,有效的步数取决于你需要提高你的基数,以实现这样一个小数目,乘以n会产生比1更小的数字。这对应于对数的定义,我已经开始了我的答案。

编辑:

想想这样:你有n作为输入,你在哪里搜索第一个k

n * .999 ^ k <1

因为你通过递增来搜索k,因为如果你在一个步骤中有l> = n,那么你将在下一步有l * .999。 重复此操作可以实现乘法算法的对数复杂度。





big-o