我不明白为什么这段代码的时间复杂度是O(logn):
至少在我的学习材料中是这样说的。
double n;
/* ... */
while (n>1) {
n*=0.999;
}
至少在我的学习材料中是这样说的。
double n;
/* ... */
while (n>1) {
n*=0.999;
}
想象一下代码如下:
double n;
/* ... */
while (n>1) {
n*=0.5;
}
希望你能够直观地看到这是O(logn),我希望。
如果您改为乘以0.999,则速度会变慢一个恒定因素,但当然复杂度仍然写为O(logn)
n
等于1或小于1之前需要多少次迭代。k
,则要解决的问题如下:
计算过程如下:n * 0.999^k = 1
对于大O符号,我们只关心“大局”,因此我们舍弃常数。这里的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)
log(0.999)
是一个负常数,因此(-1/log(0.999))是一个可以“舍弃”的正常数,即设为1。因此我们得到:
因此,代码的时间复杂度为O(logn)。k ~ log(n)
n
的初始值是多少? - Gaurav Sehgaln
值的演变。如果您的系数是0.5
会发生什么?如果是0.75
呢? - UselessO(logn)
复杂度吗?如果是的话,那么说明这个循环具有O(logn)
复杂度会更容易。如果不理解...那么你需要重新阅读课程。 - bolov