在证明Big时找到C和N是一种简单的方法
我开始学习Big-Oh符号。
给定函数的C和N0的简单方法是什么？
说，例如：
（n + 1）5或n5 + 5n4 + 10n2 + 5n + 1
我知道Big-Oh的正式定义是：
令f（n）和g（n）是将非负整数映射到实数的函数。 如果存在实常数c> 0并且整数常数N0> = 1，使得对于每个整数N> N0，f（n）<= cg（n），我们说f（n）是O 。
我的问题是，为c和N0选取值的好方法是什么？
对于上面给定的多项式（n + 1）5，我必须证明它是O（n5）。 那么，我应该如何选择我的C和N0，以便我可以在不猜测的情况下使上述定义成立？
您可以通过添加多项式中每项的系数来选择一个常数c。 以来
| n5 + 5n4 + 0n3 + 10n2 + 5n1 + 1n0 | <= | n5 + 5n5 + 0n5 + 10n5 + 5n5 + 1n5 |
并且你可以简化双方得到
| n5 + 5n4 + 10n2 + 5n + 1 | <= | 22n5 |
所以c = 22，并且对于任何n> = 1这总是成立的。
几乎总是可以通过提高N0来找到一个更低的c，但是这种方法很有效，而且你可以在脑海中做到这一点。
（多项式周围的绝对值运算应考虑负系数。）
通常，证明没有选择具体的C和编号而不是证明f（n）<C * g（n），证明f（n）/ g（n）<C.
例如，要证明n3 + n是O（n3），请执行以下操作：
（n3 + n）/ n3 = 1 +（n / n3）= 1 +（1 / n2）<2，这里你可以选择任何C> = 2且No = 1。
你可以检查lim abs（f（n）/ g（n））是什么时候n - > + infitity，并且会给你常量（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））存在并且小于+ infinity。
链接地址: http://www.djcxy.com/p/39729.html上一篇: What is an easy way for finding C and N when proving the Big