如何比较指数复杂度？
How to compare exponential complexities?
我有一个在 O(√x) 中运行的算法，其中 x 是我的输入。
现在，我不想使用 x，而是使用 x 的位数，即 n。我知道x = O(2ⁿ)，所以我的算法应该是O(√x) = O(2<sup>n/2</sup>)。对吗？
我无法理解的是，据我所知，O(2<sup>n/2</sup>) 等同于O(2ⁿ)（换句话说：2<sup>n</sup> 和 2<sup>n/2</sup> 以同样的速度增长）。但这不可能是正确的，因为这意味着 O(√x) 等价于 O(x)，这是错误的（x 和 √x 不会以相同的速度增长） .
我做错了什么？
你的假设是 O(2<sup>n</sup>) 和 O(2<sup>n/2</sup>)相等，是错误的。
limn → ∞ 2n/2n/2 = limn → ∞ 2n/sqrt(2)n = limn → ∞ (2/sqrt(2))n = ∞
因此2<sup>n/2</sup>在o(2<sup>n</sup>) (小-o).
一般来说：令a,b ∈ ℝ.
= ∞ ∀ a > b ⇒ aⁿ ∈ ω(bⁿ)
limn → ∞ an/bn = limn → ∞ (a/b)n = 1 ∀ a = b ⇒ aⁿ ∈ Θ(bⁿ)
= 0 ∀ a < b ⇒ aⁿ ∈ o(bⁿ)
O(2<sup>n/2</sup>) 不等同于O(2<sup>n</sup>) !
就 O 表示法而言，在谈论指数行为时，不同的基数并不等价。
我有一个在 O(√x) 中运行的算法，其中 x 是我的输入。
现在，我不想使用 x，而是使用 x 的位数，即 n。我知道x = O(2ⁿ)，所以我的算法应该是O(√x) = O(2<sup>n/2</sup>)。对吗？
我无法理解的是，据我所知，O(2<sup>n/2</sup>) 等同于O(2ⁿ)（换句话说：2<sup>n</sup> 和 2<sup>n/2</sup> 以同样的速度增长）。但这不可能是正确的，因为这意味着 O(√x) 等价于 O(x)，这是错误的（x 和 √x 不会以相同的速度增长） .
我做错了什么？
你的假设是 O(2<sup>n</sup>) 和 O(2<sup>n/2</sup>)相等，是错误的。
limn → ∞ 2n/2n/2 = limn → ∞ 2n/sqrt(2)n = limn → ∞ (2/sqrt(2))n = ∞
因此2<sup>n/2</sup>在o(2<sup>n</sup>) (小-o).
一般来说：令a,b ∈ ℝ.
= ∞ ∀ a > b ⇒ aⁿ ∈ ω(bⁿ)
limn → ∞ an/bn = limn → ∞ (a/b)n = 1 ∀ a = b ⇒ aⁿ ∈ Θ(bⁿ)
= 0 ∀ a < b ⇒ aⁿ ∈ o(bⁿ)
O(2<sup>n/2</sup>) 不等同于O(2<sup>n</sup>) !
就 O 表示法而言，在谈论指数行为时，不同的基数并不等价。