While循环的时间复杂度为O(logn)。

Question

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

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

至少在我的学习材料中是这样说的。

- Muushuu Pip

---

n的初始值是多少？ - Gaurav Sehgal

无所谓 @GauravSehgal - alain

@GauravSehgal：这并不影响循环的时间复杂度。 - Andre Kampling

审查n值的演变。如果您的系数是0.5会发生什么？如果是0.75呢？ - Useless

你理解 O(logn) 复杂度吗？如果是的话，那么说明这个循环具有 O(logn) 复杂度会更容易。如果不理解...那么你需要重新阅读课程。 - bolov

Answer 1

想象一下代码如下：

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

希望你能够直观地看到这是O（logn），我希望。

如果您改为乘以0.999，则速度会变慢一个恒定因素，但当然复杂度仍然写为O（logn）

- Retr0id

---

是的，这是最容易理解的方式。 - bolov

Answer 2

您想计算在n等于1或小于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)。

- Support Ukraine

Answer 3

对数有两个输入：底数和数字。对数的结果是你需要把底数提高到达到给定数字的幂次。由于你的底数是0.999，数字是小于1的第一个数字，你有一个标量n，有效步数取决于你需要提高底数以实现这样一个小数字的幂次，乘以n将得到比1更小的数字。这对应于我在答案中开始的对数的定义。

编辑：

这样考虑：你有n作为输入，你搜索第一个k，其中

n * .999^k < 1

因为你通过增加k来搜索k，如果在一步中你有l >= n，则下一步将有l * .999。重复这个过程可以实现你的乘法算法的对数复杂度。

- Lajos Arpad