我有一个家庭作业问题，要求我们证明 2n+5 是 O(n²)。
这就是我试图解决它的方法：
我选择了 k = 1 并假设 n > 1 所以 f(n)/g(n) = (2n+5)/n² < (2n+5n)/n² = 7n/n² = 7/n
所以，因此 C 等于 7/n 因此，2n+5 <= (7/n)(n²) 所以 2n+5 <= 7n 这对于所有 n > 1 都是正确的。这就是为什么 2n+5 是 O( n²)。
我只是不确定这是否正确。我不是 100% 肯定，但如果有人能证实那会很棒。
此外，我对另一个要求简化为 theta 表示法的问题感到困惑：
(x 4.2 )/(1+x²)。那只是 Θ(x 2.2 )，因为我刚刚将它评估为无穷大吗？
另外，x³⋅lg(x) 我不知道从哪里开始。
提前致谢！
（最后有一个 TLDR 专门针对您的问题，我想我也会给您一些关于 big-O 的信息）
也许比形式主义更明显的东西：这个 O 符号的东西应该根据它们的增长来比较函数。如果您根据多项式的增长来比较多项式，那么您只需要查看最高指数（即它们的“度数”）：如果它们具有相同的度数，那么它们彼此的增长速度差不多。如果一个人的学历比另一个人高，那么学历高的人比另一个人增长得更快。
因此，从那和一些中学数学中，我们立即知道 2n+5 = O(n^2)，因为任何二次函数（n^2 具有正因子）在某些时候都会超过任何线性函数。
现在回到形式主义；我们还想捕捉两个函数增长“大致同样快”的想法。例如，所有正增长的线性函数的增长速度大致相同。为此，我们要引入比例因子 c：如果 f(n) <= c*g(n)，我们说 f = O(g)。通过这种缩放，我们立即看到所有线性函数都“大致同样快”地增长：取 f(n) = a*n + b 和 g(n) = k*n + d，然后您可以使用缩放因子重新缩放 g a/k 得到 a/k * g(n) = a*n + d*a/k；所以现在 a/k * g(n) 和 f(n) 增长同样快，它们的绝对差值减小到一个恒定值。
对于线性和二次函数，我们不能这样做；无论我们如何重新调整线性函数，二次函数总是会增长得更快。例如，您可以从它们的衍生物中看到这一点；线性函数的导数是常数，二次函数的导数是线性函数，所以二次函数的增长总是增加而线性函数的增长保持不变。
big-O 定义的最后一部分是关于“对于所有 n > n_0 对于某些 n_0”；我们这样做的原因是因为即使 g 增长得比 f 快，最初 f 可能具有更高的值。例如比较 g(n) = n^2 和 f(n) = n + 2^200。最初，无论你重新缩放多少，f(1) 都将大于 c*g(1)。我们不想打扰这样的事情，所以我们说“如果在某些时候 c*g 高于 f 并保持在它之上，这对我们的目的来说已经足够了”。这就是“（存在 ac 这样）存在 n_0 使得对于所有 n > n_0: f <= c*g” 出现的地方。
现在回到你的问题：你想证明存在 ac 和一个 n_0，这样对于所有 n > n_0，我们有 2n+5 <= c*n^2。现在你必须确定的是 c 是一个数字，而不是一个函数，所以设置 c = 7/n 是不可能的。但是你实际上可以选择一个任意的正 c 看看你是否能解决这个不等式；我将在 c = 3 时展示它：
2n+5 <= 3*n^2
0 <= 3*n^2 - 2n - 5
现在 3*n^2 - 2n - 5 的根是 10/6 和 -1，这意味着在 -1 之前，不等式成立，在 -1 和 10/6 之间，我们低于 0，而在 10/6 之后，不等式再次持有。这意味着我们选择 10/6 之后的第一个自然数作为我们的 n_0，所以我们得到 n_0 = 2。
关于 x^4.2/(1+x^2)，对于 x > 1 和 x^4.2，我们得到 0.5*x^2.2 = x^4.2/(2x^2) < x^4.2/(1+x^2) /(1+x^2) < x^4.2/x^2 = x^2.2 对于所有正 x。
对于 x^3 lg x，你就完成了，没有更简单的表达式。您当然可以在不使用对数的情况下给出上限，但实际上并非必须如此。
2n+5 是 O(n^2)
如果您选择 k = 1，那么您需要找到 n0 使得对于所有 n > n0，n^2 > 2n + 5。例如 n0 = 4。另一种方法是在计算 lim 2n+5/n^2 时n -> inf。因为 lim (n->inf) 2n+5/n^2 = 0，我们可以说 2n+5 是 o(n^2) (small o) 这意味着大 O 符号 2n + 5 是 O(n^2 ）。
(x^(4.2))/(1+x^2)可以合理地说它是 Theta(x^2.2) 因为你可以找到常数 k1, k2 使得对于所有 x>x0, k1*x^2.2 <= (x^(4.2))/(1+x^2) <= k2 * x^2.2。
x^3*lg(x)
最合理的答案是 x^3*lg(x) 是 O(x^4)，因为 lg(x) 是 O(x) 和大 O 符号乘积属性。