O(n)与O(nlogn)时间复杂度比较

Question

我在网上看到了这个关于时间复杂度的例子，但是有些困惑。

x = n
while ( x > 0 ) {
    y = x
    while ( y > 0 ) {
        y = y - 1
    }
    x = x / 2
 }

答案被表述为O(n)。我想知道为什么不是O(nlogn)。我这么说的原因是因为外层循环看起来是对数级别的，而内层循环则是线性的。如果y=n（而不是x），那么时间复杂度会变成O(nlogn)吗？如果是，为什么？

- sdweldon

---

它既是O(n)又是O(n log n)，但是BigTheta(n)：https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann%E2%80%93Landau_notations - kfx

Answer 1

执行 y=y-1 会运行多少次？这将衡量复杂度，对吗？

• 当 x=n 时，它会运行 n 次。
• 当 x=n/2 时，它会运行 n/2 次。
• 当 x=n/4 时，它会运行 n/4 次。
• ...

因此，它会运行 n + n/2 + n/4... 直到总和为 2n。

因此总的复杂度是 O(n)。

不要被骗了，内部循环是线性的，但并不独立于外部循环。

- Jean-Baptiste Yunès

Answer 2

内部循环确实是线性的，但每次迭代并不需要 n 步，而是需要当前值为 x 的 x 步，这个值会逐步减半，因此可以进行更精细的分析。您高估了内部循环的成本。因此，限制条件为

O(n log n)

也是正确的，但

O(n)

这是一个较小的界限。可以通过推理看出较小的界限，即内部循环的第i次迭代所需时间。

n / 2^i

步骤; O(n) 的运行时间上界源于分母之和是 等比数列，其收敛到常数 2。

- Codor

---

但是当 n -> ∞ 时，这个级数只有在 n = 2 的情况下才会收敛，否则表达式的和将会是 ∞。 - Karan Modi

@KaranModi 我不确定我是否理解了你的评论；这个级数从下面收敛，每个部分和都小于2。 - Codor

我的错误，这个级数确实收敛。 - Karan Modi