问题是要证明
- f(n) = 4n 5 - 17n 4 - 33n 3 - 13n 2
在 Θ(n 5 )
我尝试将 4n 5分成两个单独的常数 (2n 5 + 2n 5 ) 并使整个方程大于或等于 2n 5并得到 C = 2, N >= 6。
我不确定我是否正确，我仍然不确定如何实际证明该函数在 Θ(n 5 ) 中。我希望有人能来帮助我解决这个问题，以及为了证明其他 Big Oh 符号问题需要采取哪些步骤。
谢谢你们的帮助！
问问题
3282 次
1 回答
4
f(n) ∈ Θ(g(n)) （更一般）：
我们必须证明存在积极M的，N这样
g(n) * M <= f(n) <= g(n) * N
对于足够大的ns。在这种情况下，就是
M * n 5 <= 4n 5 - 17n 4 - 33n 3 - 13n 2 <= N * n 5
除以：n5
M <= 4 - 17(1/n) - 33(1/n 2 ) - 13(1/n 3 ) <= N
对于大ns，我们将留下
M <= 4 - ε <= N
我们可以选择M = 3和N = 4。
f(n) ∈ O(g(n)) （更具体）：
这实际上是从上面的结果得出的，但我们也可以提供一个具体的证明。
我们必须证明存在一个正数N使得
|f(n)| <= g(n) * N
对于足够大的ns。在这种情况下，就是
|4n 5 - 17n 4 - 33n 3 - 13n 2 | <= N * n 5
除以：n5
4 - 17(1/n) - 33(1/n 2 ) - 13(1/n 3 ) <= N
对于大ns，我们将留下
4 - ε <= N
我们可以挑N = 4。
参考：
于 2013-10-19T22:10:53.437 回答