大O符号：n^2 = Ω(n log n)？

Question

Ω(n log n)是否意味着n^2？

额外说明：能否有人用图示的方式清晰地解释一下大O、Θ和Ω的含义？

- CarolineRudolph

---

请看这个链接：https://dev59.com/-HRB5IYBdhLWcg3w3K0J - Gregor Valentin

Answer 1

n^2 = Ω(n log n) 不是相等关系，而是这些函数之间的关系。
您可以在这里阅读相关内容并查看示例。

- zardav

Answer 2

这不是，它是Omega，意思是“渐进地相同或更低”。

在“渐进”方程中，它与n^2 >= n log n相同。

---

额外：

标准方程 || 文本表示 || 渐近方程

f(x) = O(g(x)) || g(x) is asymptotically same or higher as f(x) || f(x) <= g(x)
f(x) = Θ(g(x)) || g(x) is asymptotically same as f(x) || f(x) = g(x)
f(x) = Ω(g(x)) || g(x) is asymptotically same or lower as (fx) || f(x) >= O(g(x))

PS：请注意，如果f(x) = O(g(x))，那么也意味着g(x) = Ω(f(x))，这类似于如果f(x) <= g(x)，则g(x) >= f(x)

- libik