我开始学习 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 使得 f(n) <= cg(n) 对于每个整数 N > N 0。
我的问题是，为 c 和 N 0选择值的好方法是什么？
对于 (n+1) 5上面的给定多项式，我必须证明它是 O(n 5 )。那么，我应该如何选择我的 c 和 N 0以便我可以在不猜测的情况下使上述定义为真？
您可以通过添加多项式中每个项的系数来选择常数 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 ，但是这种方法有效，您可以在脑海中做到这一点。
（多项式周围的绝对值运算要考虑负系数。）
通常证明是在不选择具体的 C 和 N 0的情况下完成的。您无需证明 f(n) < C * g(n)，而是证明 f(n) / g(n) < C。
例如，要证明 n 3 + n 是 O(n 3 )，您可以执行以下操作：
(n 3 + n) / n 3 = 1 + (n / n 3 ) = 1 + (1 / n 2 ) < 2 对于任何 n >= 1。在这里您可以选择任何 C >= 2 且 N 0 = 1 .
您可以检查当 n->+infitity 时 lim abs(f(n)/g(n)) 是什么，这将为您提供常数 (g(n) is n^5 in your example, f(n) is (n+1)^5)。
请注意，对于 x->+infinity，Big-O 的含义是，如果 f(x) = O(g(x))，则 f(x)“增长速度不会比 g(x)”快，所以你只需要证明 lim abs(f(x)/g(x)) 存在且小于 +infinity。
这将在很大程度上取决于您正在考虑的功能。但是，对于给定的函数类，您可能会想出一个算法。
例如，多项式：如果将 C 设置为大于多项式的前导系数的任何值，则可以求解 N 0。
在你理解了那里的魔力之后，你还应该知道 big-O 是一个符号。这意味着你不必在你解决的每一个问题中寻找这些系数，一旦你确定你理解了这些字母背后发生的事情。您应该只根据notaion操作符号，根据其规则。
没有简单的通用规则来确定 N 和 c 的实际值。你应该回忆你的微积分知识来解决它。
big-O 的定义与 limit的定义纠缠在一起。它使 c 满足：
c > lim |f(n)/g(n)|，给定 n 接近 +无穷大。
如果序列是有上限的，它总是有一个限制。如果不是，那么 f 不是 O(g)。在你选择了具体的 c 之后，你将毫无问题地找到合适的 N。