大 O 作为双方的指数？
Big O as an exponent on both sides?
假设我们有一个像
这样的表达式
2f(n) = O(2g(n))
我不明白这个表达。我知道 f(n) = O(n) 是什么。它基本上意味着左侧在 O(n) 处渐近有界。
O 是大 O 符号。
基本上它意味着 2<sup>g(n)</sup> 是 2<sup> 的渐近上限f(n)</sup>.
现在可以认为这与f(n) ∈ O(g(n))相同，但这只是在一个方向上是正确的。
2f(n) ∈ O(2g(n)) ⇒ f(n) ∈ O(g(n))
但是反过来就不对了
例如：
f(n) = 2n, g(n) = n 所以
2n ∈ O(n) 成立，但 2<sup>2n</sup> = 4<sup>n</sup> ∉ O(2<sup>n</sup>).
假设我们有一个像
这样的表达式2f(n) = O(2g(n))
我不明白这个表达。我知道 f(n) = O(n) 是什么。它基本上意味着左侧在 O(n) 处渐近有界。
O 是大 O 符号。
基本上它意味着 2<sup>g(n)</sup> 是 2<sup> 的渐近上限f(n)</sup>.
现在可以认为这与f(n) ∈ O(g(n))相同，但这只是在一个方向上是正确的。
2f(n) ∈ O(2g(n)) ⇒ f(n) ∈ O(g(n))
但是反过来就不对了
例如：
f(n) = 2n, g(n) = n 所以
2n ∈ O(n) 成立，但 2<sup>2n</sup> = 4<sup>n</sup> ∉ O(2<sup>n</sup>).