algorithm - 函数的渐近增长

Question

如何确定给定的 f(n) 和 g(n) 是在 theta、omega、big oh、little omega 还是 little oh 中？- 我认为一种方法是绘制函数 f(n) 和 g(n) 的图形。即使通过绘制图表，当 f(n) 在 theta、omega、大 oh、小 omega 或小 oh 中时，我们怎么说？我不清楚。有人可以提供更多详细信息吗？

我也不确定这是不是正确的方法。谁能告诉我是否还有其他更简单的方法可以做到这一点。举个例子:f(n) = sq root(n) and g(n) = n^sin n

Answer 1

您不能通过目测来确定渐近增长。每种类型的渐近增长关系都有正式定义，可以准确准确地解释它们的含义。您可以通过数学确定它们是否满足关系的正式定义来确定两个函数是否符合给定关系。

例如，Big-O 的几个等价形式定义之一如下:

f = O(g) if and only if lim [ n -> inf ] ( f(n) / g(n) ) < inf

因此，例如，如果 f(n) = n，并且 g(n) = n^2，您可以观察到极限为 n -> n/n^2 的无穷大 = 0，因此 f = O(g).

或者，如果 f(n) = n 且 g(n) = 2n，您可以观察到 n-> inf，n/2n -> 1/2 < inf，所以 f = O(g)。

但是，如果 f(n) = n 且 g(n) = sqrt(n)，您可以观察到极限为 n -> n 的无穷大/sqrt(n) = 无穷大，因此 f != O( g).

您的示例 f 和 g 很棘手，因为随着 n 的增加，正弦在 -1 和 1 之间振荡。但是 Wolfram Alpha 告诉我所讨论的极限是无穷大，所以 sqrt(n) != O(n^(sin(n)).

每个其他渐近增长关系都有一个相似的正式定义，您可以测试两个函数是否相互满足它。

编辑:

您似乎在寻找经验法则。下面是确定相对简单的函数 f 和 g 的渐近阶的快速简便的方法。考虑每个函数中 n 的最高次幂:

• 如果最高次幂相同，则f = O(g), g = O(f), f = Omega(g), g = Omega(f), f = Theta(g), g = Theta (六)
• 如果f中的最高次幂小于g中的最高次幂，则f = O(g), f = o(g), g = Omega(f), g = omega(f)
• 如果f中的最高次幂大于g中的最高次幂，则f = Omega(g), f = omega(g), g = O(f), g = o(f)

当然，如果函数不是 n 的多项式，或者更复杂并且不容易确定最高次幂是多少(例如，您的示例使用正弦)，您仍然必须恢复到正式定义。

一些永远正确的事情:

• 根据定义，Theta 是 O 和 Omega 的结合。 f = O(g) ^ f = Omega(g) <=> f = Theta(g) [其中 ^ 表示逻辑“与”]
• “小”关系比“大”关系强。这意味着 f = o(g) => f = O(g) 和 f = omega(g) => f = Omega(g)，但相反的方向是不正确的。