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。我在 Whosebug 上看到了同样的问题，但没有一步一步的解决方案

Answer 1

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

让我们举几个例子：

n^4 < 2*n^4，对于所有 n>1。
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.

Answer 2

据我所知，我们可以用一种简单的方法解决这个问题:-

n^4+100*n^2+50 -- 让我们通过假设 n^2 = t
t^2+ 100*t+50 -- 等式变化如前所述
使用二次方程并求解这个方程 (t^2+100*t+50) 我们得到两个答案。
t = -100 +/- sqrt( 100^2 - 4*1*50)/2.1
t = -71.8 & -128.2 -- 现在将值替换回 n^2
n^2 = -71.8 & -128.2
n = sqrt(-71.8) & sqrt(-128.2) = 8.47 & 11.32 -- 查看上限数字并尝试解决第一个可以替代 n 的最大数字。
n = 11 因此，我们将 n = 11 作为可用于查找上限的第一个最大数

希望对您有所帮助！

Answer 3

n^4 + 100n^2 + 50 <= 2n^4 , for all n>=11.

因为直到10，n都会有负值。

Answer 4

n0 的答案是 11 因为如果我们假设 n 值 =11 和 c 值 2 ，那么条件满足大 oh 符号 f(n)<=O g(n)，把 n =11 并求解二次方程，你会得到你的答案尝试在数学上使用它。谢谢.

Answer 5

我们需要找到最小的增长率 g(n) 使得

c g(n) >= f(n) 对于 n>=k。

对于 c 和 k 的某个常数值，上述等式将成立。我们不考虑较低的 n 值。这意味着对于较低的 n 值，g(n) 并不重要。对于较大的 n 值，g(n) 将是 f(n) 的最大增长率。

这里，f(n)= n^4 + 100 n^2 + 50

当n很大时，g(n) = n^4

求c和k，使得c n^4 >= n^4 + 100 n^2 + 50

如果我们舍弃 100 n^2 和 50 的低项。我们可以说 c 应该是 2。

2 n^4 >= n^4 .

要找到 k 的值，请尝试替换 n^2 = t、n^4 = t^2 和 c=2，

2t^2 >= t^2 + 100t + 50

t^2 >= 100t +50

如果我从 1、2、3、4、5,6、7、8、9 和 10 开始输入 t 的值，并且 t^2 =100

10岁了，我还有

100,00 <= 100, 00 +50

在 t= 11，t^2 = 121，我有以下

14,641 >= 12150.

所以我的 k 将是 11。

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

What's the upper bound of f(n) = n^4 + 100n^2 + 50?

algorithm

big-o

complexity-theory

asymptotic-complexity