big-o - o 符号和 o 符号

Question

如果f(n) = Θ(g(n))那时我知道f(n)=O(n)和f(n) = Ω(g(n))，那么我会说应该存在 c1 和 c2 ≥ 0，n1 ≥ 0，对于所有 n > n1，存在c1*g(n) ≤ f(n) ≤ c2*g(n)。

证明f(n) = c*g(n) + o(g(n))一些 c > 0。我的观点是f(n) ≤ c2*g(n)==> 我们有f(n) < c2*g(n) + c*g(n) ==> fn ≤ c2*g(n) < (c2 + c)*g(n). 因此，我想说f(n) = c*g(n) + O(g(n))对于某些 c > 0 是正确的。正确吗？

我也可以说f(n) = cg(n) + o(g(n))，对于某些 c > 0？

Answer 1

f(n) = Θ(g(n))然后我知道f(n) = O(n)和f(n) = Ω(g(n))。

好吧，绝对不是。看，当f(n) = Θ(g(n))它意味着这f(n)是一组渐近增长不快于 的函数时g。g什么时候n^2,f(n)成为一组增长不快于 的函数n^2绝对不等于一组增长不快于 的函数n^2。这是因为存在一个元素在第二个集合中，而不是第一个。是h(n) = n^2。

Quod erat 示范