algorithm - 渐近分析比较 f 和 g

Question

我必须比较函数 f 和 g 以确定是否:

f ∈ Θ(g), f ∈ O(g),f ∈ o(g), f ∈ Ω(g),f ∈ ω(g), g ∈ Θ(f), g ∈ O(f), g ∈ o(f), g ∈ Ω(f), g ∈ ω(f)。

f(n) = n^2/log n 和 g(n) = n log n。

作为我对渐近分析的理解，我得到了:

    f(n) = O(g(n)) is like a =< b
    f(n) = Ω(g(n)) is like a => b
    f(n) = Θ(g(n)) is like a == b
    f(n) = o(g(n)) is like a < b
    f(n) = ω(g(n)) is like a > b

所以现在我绘制了 f(n) 和 g(n)，我看到对于较小的 n 值，f(n) 更大，但是对于非常大的 n 值，g(n) 更大，所以在这种感觉当 n 更大时更重要，因为算法必须是通用的，所以这意味着 f(n) 和 g(n) 是:

f ∈ Ω(g) and f ∈ ω(g) and g ∈ O(f) and g ∈ o(f)

现在我的问题是，这是找到这些的正确方法，以便绘制函数并查看哪个更大，这是否意味着当它们相交时它们相等？

Answer 1

在这两种情况下你的理解看起来是错误的:

f(n) = o(g(n)) is like a < b
f(n) = ω(g(n)) is like a > b

最好将这些情况可视化为:

f(n) = o(g(n)) is like a << b
f(n) = ω(g(n)) is like a >> b

不好意思，这两个符号的确切数学含义<< (“少得多”)和 >> (“更大”)未定义。

因此，一般来说，您可以考虑比率的限制，而不是绘制两个函数 f(n)/g(n)这两个函数(当 n 变为正无穷大时):

• 如果此限制为零，则 f = o(g)
• 如果这个限制是一个正常数，那么f = Θ(g)
• 如果这个极限是正无穷大，那么f = ω(g)

当然，这只是一个提示 - 如果您对这种关系使用精确的数学定义，那么您对任何有关两个函数之间渐近关系的问题的回答看起来会好得多。