Ω(n log n)是否意味着n^2?
额外说明:能否有人用图示的方式清晰地解释一下大O、Θ和Ω的含义?
Ω(n log n)是否意味着n^2?
额外说明:能否有人用图示的方式清晰地解释一下大O、Θ和Ω的含义?
这不是,它是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)