algorithm - f(n) = n^4 + 100n^2 + 50 的上限是多少？

Question

我正在解决一些与 Big-O 相关的练习，但我卡在了这个练习上:

Exercise - Find upper bound for f(n) = n^4 + 100n^2 + 50

我试图一步一步解决它，但出了点问题......:

1.=> n^4 + 100n^2 + 50 <= O(g(n))
2.=> n^4 + 100n^2 + 50 <= Cn        ** Added -n^4 to both sides
3.=> n^4 + 100n^2 + 50 -n^4 <= Cn -n^4
4.=> 100n^2 + 50 <= Cn - n^4         ** Put n in common
5.=> 100n^2 + 50 <= n(C - n^3)       ** Divided n in the opposite site
6.=> (100n^2 + 50)/n <= C -n^3       ** Assumed 1 for n
7.=> 100 + 50 <= C - 1                      
8.=> 151 <= C

有问题，因为答案是 c = 2 和 n=11。我在 stackoverflow 上看到了同样的问题，但没有一步一步的解决方案

Answer 1

很容易猜到这个函数的上界是 O(n^4)，因为 k * n^4 可以压倒 n^3 的任何倍数和其他小于 4 的 n 的倍数，经过n 的特定值(其中 k 是倍数)。

让我们举几个例子:

1. n^4 < 2*n^4，对于所有 n>1。

2. n^4 + n^3 < 2*n^4，对于所有 n>2。

在您的情况下，您需要找到满足方程式的系数 K，例如 n^4 + 100n^2 + 50 <= k * (n^4)。

我会把正确的方程留给你来解决，因为你展示的那个显然是不正确的:

n^4 + 100n^2 + 50 <= O(g(n))
n^4 + 100n^2 + 50 <= O(n^4)
n^4 + 100n^2 + 50 <= k * n^4
n^4 + 100n^2 + 50 <= n^4 + 100*n^4 + 50*n^4
n^4 + 100n^2 + 50 <= 151 * (n^4)
// O(n^4) achieved, for all n >= 1.

你可以通过将n^2 代入t 将其转化为二次方程来求解该方程，然后方程简化为:

t^2 + 100t + 50 <= k * t^2
// left for you to solve this.
// check for what value of `k` and `t`, this equation gets satisfied.