我正在解决一些与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上看到了同样的问题但没有一步一步的解决方案
猜测这个函数的上界是O(n ^ 4)是非常简单的,因为k * n ^ 4可以超过n ^ 3的任意倍数和n的低于4的其他倍数,在某个值之后n(其中k是倍数)。
我们来举几个示例:
在您的情况下,您需要找到满足您的方程的系数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.
据我所知,我们可以通过一种简单的方式解决这个问题: -
希望能帮助到你!