为什么时间复杂度 O(2^N ) 不能降低到 O(2*2*2*...*2^0)=O(1)？

Question

考虑时间复杂度 O(5N²)。通过消除常数因子 5，我们将时间复杂度表示为 O(N²)。

现在，如果时间复杂度为 O(2^N)，我们可以将其重写为 O(2⋅2^N-1)。然后通过消除常数因子 2，我们可以将其再次重写为 O(2^N-1)。

但是，如果我们无限期地继续这个过程，每次都减少指数，时间复杂度最终将是 (2⁰)，或 O(1)。

这个逻辑有什么缺陷？

Answer 1

我想更详细地扩展 @wohlstad 的评论。在你的问题中，你写道：

但是，如果我们无限期地继续这个过程，每次都减少指数，时间复杂度最终将是 (2^0)

问题是，时间复杂度永远不会为零，即使你无限期地这样做。由于 N 是任意大的，因此您始终可以从中再减去 1，并且仍然会留下一个正数，无论您执行多少次。因此，即使迭代次数不定，您也永远无法达到 O(20)。 思考这个问题的另一种方法是考虑大 O 表示法的定义。这种方法并不能

识别

你的逻辑缺陷，但它确实证明了它的存在。套用维基百科：

函数 f(x) 的阶数为 O(g(x))，如果对于某个正实数 M，

|f(x)| ≤ M * g(x)

对于超过某个点的所有 x。

也就是说，f(N) = 5N

2

的阶数为 O(N²)，因为对于所有 N > 0（或任何其他数字），|5N²| ≤ 5 * N²。在此示例中，M 是正实数 5。 但是如果你应用你的方法，M就不会是一个正实数。这将是无限乘积

2*2*2*2*2...

，它是发散的并且不是真实的。这意味着 f(x)

不能

是 O(1)，因此任何认为它是 O(1) 的论点必定存在一些致命缺陷。