11 big-o
我开始学习Big-Oh符号了.
找到给定函数的C和N 0的简单方法是什么？
比方说,例如:
(n + 1)5,或n 5 + 5n 4 + 10n 2 + 5n + 1
我知道Big-Oh的正式定义是:
设f(n)和g(n)是将非负整数映射到实数的函数.我们说f(n)是O(g(n)),如果有一个实常数c> 0且整数常数N 0 > = 1,那么每个整数N的f(n)<= cg(n)> N 0.
我的问题是,为c和N 0选择值的什么是一个好的,可靠的方法？
对于上面给定的多项式(n + 1)5,我必须证明它是O(n 5).那么,我应该如何选择我的c和N 0以便我可以在不猜测的情况下使上述定义成立？
Bil*_*ard 10
您可以通过在多项式中添加每个项的系数来选择常数c.以来
| n 5 + 5n 4 + 0n 3 + 10n 2 + 5n 1 + 1n 0 | <= | n 5 + 5n 5 + 0n 5 + 10n 5 + 5n 5 + 1n 5 |
你可以简化双方来获得
| n 5 + 5n 4 + 10n 2 + 5n + 1 | <= | 22n 5 |
所以c = 22,对于任何n> = 1,这总是成立.
几乎总是可以通过提高N 0找到较低的c ,但这种方法有效,你可以在脑海中做到这一点.
(多项式周围的绝对值运算是为了计算负系数.)
小智 2
您可以检查当 n->+infitity 时 lim abs(f(n)/g(n)) 是什么，这将为您提供常数（g(n) 在您的示例中为 n^5，f(n) 为(n+1)^5)。
请注意，x->+无穷大的 Big-O 的含义是，如果 f(x) = O(g(x))，则 f(x)“增长不比 g(x) 快”，所以您只需要证明 lim abs(f(x)/g(x)) 存在且小于 +无穷大。