大O符号证明

Question

问题是要证明：

• f(n) = 4n⁵ - 17n⁴ - 33n³ - 13n²

属于 Θ(n⁵)。

我尝试将4n⁵拆分成两个常数（2n⁵ + 2n⁵），并使整个方程大于或等于2n⁵，得到C=2，N≥6。

我不确定自己是否正确，也不太确定如何实际证明函数属于Θ(n⁵)。希望有人能帮助我解决这个问题，并告诉我证明其他Big Oh符号问题的步骤。

谢谢大家的帮助！

- Matt

---

实际上，你只需要查看定义。1：对于任何自然数，f(n) <= 4n^5（因为所有其他项都是负数）。2. 对于 n >= 10，n^5 <= f(n)（对于 n = 10，所有低阶项最多从第一项中取 ~2n^5）。 - Zeta

这更适合放在 [cs.se] 或 [math.se] 上讨论。 - millimoose

你目前了解的 Landau 符号规则有哪些？导数规则？极限规则？还是仅仅是定义？ - G. Bach

在维基百科上：https://en.wikipedia.org/wiki/Big_O_notation。你可以证明根据大O符号的定义。 - gongzhitaao

现在，只有定义。 - Matt

Answer 1

f(n) ∈ Θ(g(n)) (更为通用):

我们需要展示存在正整数的M和N，使得：

g(n) * M <= f(n) <= g(n) * N

对于足够大的n，有：

M * n5 <= 4n5 - 17n4 - 33n3 - 13n2 <= N * n5

除以n5：

M <= 4 - 17(1/n) - 33(1/n2) - 13(1/n3) <= N

对于足够大的n，我们会得到：

M <= 4 - ε <= N

我们可以选择M = 3和N = 4。

---

f(n) ∈ O(g(n)) (更具体):

这实际上是基于上面的结果，但我们也可以提供一个具体的证明。

我们必须证明存在一个正的N，使得

|f(n)| <= g(n) * N

对于足够大的n，可以得到以下不等式：

|4n5 - 17n4 - 33n3 - 13n2| <= N * n5

将其除以n5：

4 - 17(1/n) - 33(1/n2) - 13(1/n3) <= N

对于足够大的n，我们会得到如下结果：

4 - ε <= N

我们可以选择N = 4。

---

参考资料：

• 巴赫曼-朗道符号家族

- arshajii

---

@gongzhitaao，我认为Θ无论上限还是下限都是有界的。请参见http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations。 - arshajii

@Matt 但是你的问题要求Θ而不是O... - Donal Fellows

@Matt，我都包含了，请看编辑。 - arshajii

@arshajii 谢谢您的编辑。我看到您写了4n5 + 17n4 + 33n3 - 13n2。我可以问一下为什么您将n^4和n^3的符号从负数改为正数，而保留n^2？当我们找到M和N的值时，我们如何证明该函数是n^5的大O元素？再次感谢您的回复！ - Matt

@arshajii 谢谢，我也想知道 4 - ε 是用来干什么的？一旦我们找到 M / N 的值，我们如何证明函数是 n^5 的大O函数呢？感谢您。 - Matt