algorithm - 函数的渐近分析

Question

如何理解这类问题，我知道 big-O、big-omega 和 big-theta，但你能用例子解释一下吗？

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

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

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

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

标签： algorithmtime-complexitybig-o

Answer 1

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

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

• f(n) >= c1*n - 因为是 Omega(n)
• 我们不知道 f(n) 的任何上限。
• g(n) >= CONST - 因为它正在增长且非负数
• g(n) <= c2*n - 因为是 O(n)
• c3 n <= h(n) <= c4 n - 由于是 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))