渐近符号大O和大Ω

Question

f(n) = 6*2^n + n^2

大O = 2^n

大Ω = 2^n

在上面的等式中，大O和大Ω都有相同的值。如果大O是上界，而大Ω是下界，为什么它们两个的值相同而不是大Ω = n^2呢？

- Pegasus008

---

你确定它不是6 * 2^n吗？如果是62^n，那么我认为这是错误的。 - Ami Tavory

@AmiTavory 谢谢，我已经纠正了。 - Pegasus008

简短回答：因为 n² 相对于 2^n 来说是可以忽略的。 - user1196549

这个问题不应该发在math.stackexchange.com吗？ - MayeulC

@MayeulC 这不是一个编程问题，但它对于理解算法非常基础。 - pjs

Answer 1

真的，O和Ω是上下界限，但它们更类似于≤和≥，而不是<和>。就像可能同时a ≥ b和a ≤ b（没有矛盾），一个函数也可以是不同函数的O和Ω（实际上，这是定义Θ的方式之一）。

在这里，对于足够大的n，

• 6 2ⁿ + n² ≤ 12 2ⁿ，所以6 2ⁿ + n²最多增长（相对于乘法常数）的方式就像2ⁿ一样（它的O）。

• 相反，6 2ⁿ + n² ≥ 0.1 2ⁿ，所以6 2ⁿ + n²最少增长（相对于乘法常数）的方式就像2ⁿ一样（它的Ω）。

请注意，您无需使用相同的乘法常数。结论是6 2ⁿ + n² = Θ( 2ⁿ)。

- Ami Tavory

---

你把n²和2^n搞混了。 - user1196549

我认为这是 _6 *2^n_，实际上相当不同。 - MayeulC

@MayeulC 谢谢，我的回答中有个打字错误，但是你的评论让我在更正过程中发现了它。现在可以了吗？再次感谢。 - Ami Tavory

@AmiTavory，是的，这样好多了:)很抱歉我在这里发表了多余的评论，当我加载页面时，YvesDaoust的评论还没有出现。 - MayeulC