函数的渐近分析

Asymptotic analysis of function

如何理解这类问题，我知道big-O, big-omega 和big-theta 但你能举例说明一下吗？

PS: 1. Big-o- 它定义了算法的上限，或者通俗地说，我们可以说为了计算最坏的情况，我们使用 big-oh。

DEFN：f(n)<= cg(n) 其中 c 是常数且大于 0。 例如：对于某些算法，如果它的最坏情况是 O(n) 那么 O(n^2) 也将是上限，但我们只对最紧的上限感兴趣 bound.Right?

  1. Big-omega- 它定义算法的下限或最佳情况。 定义：f(n)>=cg(n)

与 Big-theta 类似，即算法的平均情况。

假设函数是严格的正增长函数，答案是 Omega(n)

让我们为所有函数定义边界：

  • f(n) >= c1*n - 由于是 Omega(n)
  • 我们不知道 f(n) 的任何上限。
  • g(n) >= CONST - 因为它在增长且非负数
  • g(n) <= c2*n - 由于是 O(n)
  • c3n <= h(n) <= c4n - 因为是 Theta(n)

现在让我们寻找下限 (Omega)：

T(n) = [f(n) * g(n)] + h(n) >= [c1*n * CONST] + c3*n
     = [c1*CONST + c3]*n

我们看到 T(n) 确实在 Omega(n)

现在，如果我们尝试找到一个上限，并让这个上限成为某个函数 phi(n)，我们可以得到 f(n) = phi(n) * n，它仍在 Omega(n) 中，然后：

T(n) = [phi(n)*n * g(n)] + h(n) >= [phi(n)*n * CONST] + c3*n

这是在 Omega(phi(n)*n) 中 - 因此不能在 O(phi(n))

中