我看到这个陈述，根据我的理解，Theta位于Big O和Omega之间，但我不明白为什么要使用交集。能否给我一个数学和分析的理解，Θ(g(n)) = O(g(n)) ∩ Ω(g(n))？
1个回答
9
Θ(g(n))表示函数在上下都受到g(n)的限制。
数学上，如果一个函数f(n)是Θ(g(n)), 那么
对于所有大于某个常数k的n, 有0 ≤ c1.g(n) ≤ f(n) ≤ c2.g(n)
现在,
O(g(n))是g(n)的上界，因此一个是O(g(n))的函数被g(n)所上界。
Ω(g(n))是g(n)的下界，因此一个是Ω(g(n))的函数被g(n)所下界。
O(g(n)) ∩ Ω(g(n))代表一个函数被g(n)从上下两方面夹住，如下图所示，根据定义该函数应该是Θ(g(n))。
数学上，这意味着函数对于所有大于某个常数k的n, 有0 ≤ c1.g(n) ≤ f(n) ≤ c2.g(n)。
- displayName
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
- 相关问题
- 3 g(n) ∈ O(f(n)) 是否意味着 f(n) ∈ Ω(g(n))?
- 6 如果g(n) = sqrt(n)^sqrt(n)，那么g(n)的复杂度是O(2^n)吗？
- 3 递归 G(n) 函数错误
- 3 Prove that f(n) = Θ(g(n)) iff g(n) = Θ(f(n))
- 12 证明 f(n) + g(n) 是 O(max(f(n),g(n)))。
- 3 如果f(n) = o(g(n)), 那么g(n) + f(n) = Θ(g(n))吗？
- 7 证明 n! = O(n^n)
- 3 证明如果 g(n) 是 o(f(n)), 那么 f(n) + g(n) 是 Theta(f(n))。
- 4 如果f(n) = O(g(n))，g(n) = O(h(n))，其中f、g、h是函数，请证明f(n) = O(h(n))。
- 4 算法时间复杂度与g(n)的O(n^2)复杂度是多少？