算法复杂度 Big O、Little O、Big Omega、Little Omega、Theta

Question

这是我正在处理的问题

For each pair of expressions, indicate whether A is O, o, Ω, ω, or Θ of B.

我的理解是上限，omega 是下限，theta 是上限和下限。我对小 o 和小 omega 的推断感到困惑。

我相当确定 A O of B in a since (n^3) > (n^2)，但我不确定其他一切。我想知道是否有人可以给我一些关于如何测试每一个的步骤。我查过维基百科和一些教育网站，但不是很清楚，也没有太多测试它们的例子。

谢谢

Answer 1

取自Big O notation on Wikipedia

The definitions of O-notation and o-notation are similar. The main difference lies is that in f(n)=O(g(n)), the bound 0<=f(n)<=c*g(n) holds for "some constant c>0", BUT ,in f(n)=o(g(n)), the bound 0<=f(n)<=o(g(n)) holds for "all constants c>0".

In o-notation, the function f(n) becomes insignificant relative to g(n) as n->∞ :-

// 对于严格的 little-o 表示法

lim n->∞ f(n) / g(n) = c,     `c closer to 0`  // for strict Big-O notation

同样，对于 little-omega 符号，

lim (x->infinity) f(x)/ g(x) = infinity

然而，对于严格的 Big-Omega 表示法

lim n->∞ f(n) / g(n) = c,       `c closer to ∞`

所以，现在回答你的问题，

1. lim n-> ∞ A(n)/B(n) = lim n-> ∞ {(4*n^3 - 12*n^2 + 5*n) / 36*n^2}
                         = lim n-> ∞ (n/9 - ...)
                         = ∞.

因此，A(n) 是 ω(B(n))。

2. lim n -> ∞ A(n)/B(n) = lim n-> ∞ (5^n/n^5)
                        = lim n-> ∞ (5*5*5*...n times)/(n*n*n*n*n)
                        = Depends on the value of n

因此，A(n) 是 Ω(g(n))。

另外两个留给你作为练习。如果您有任何问题，请留下进一步的评论。祝你好运解决你的问题。

算法复杂度 Big O、Little O、Big Omega、Little Omega、Theta

Algorithmic Complexity Big O, Little O, Big Omega, Little Omega, Theta

algorithm

big-o

time-complexity

bounds

big-theta