algorithm - 我们可以像估算 Big O 那样估算 Big Omega 吗？

Question

我一直在阅读估计 Big O 是多么容易:去掉最不占主导地位的项和常数。我的问题是，我们可以为 Big Omega 做同样的事情吗？

我知道输入依赖与渐近分析无关:我们可以在最佳、平均和最坏情况分析中有一个上(大 O)和下(大 Omega)。但是我对如何快速估计算法的 Big Omega 感到困惑，例如在最坏的情况下。

如果您能提供示例来澄清我的困惑，我将不胜感激。

Answer 1

仅举两个例子应该会让您有所启发。

n² + n 是 O(n²)(它也是 O(n³))。

n² + n 是 Ω(n²)(它也是 Ω(n))。

你考虑主导词。

n + (n cos n)² 是 O(n²) 和 Ω(n)。

上限和下限。