algorithm - 上限算法分析

Question

>Problem: n^4 + 100n^2 + 50. 

>Solution given: n^4 + 100n^2 + 50 <= 2n^4 for all n>=1
>                n^4 + 100n^2 + 50 = O(n^4) with c=2 and n0 = 100

但是当 n 为 1 时，上述函数将为“4+100+50 <= 2”，这是不正确的。我怎样才能得出这个问题的正确上限，或者让我知道给定的解决方案是否错误。

问题出在java中使数据结构和算法变得容易。

Answer 1

陈述解决方案的正确方法是

n^4 + 100n^2 + 50 <= c*n^4 for all n>=n0 with c=2 and n0 = 100

=> n^4 + 100n^2 + 50 = O(n^4)

Answer 2

我们需要找到最小的增长率，g(n)这样

c g(n) >= f(n) for n>=k.

对于 c 和 k 的某个恒定值，上述等式将成立。我们不考虑较低的 n 值。这意味着g(n)对于低值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^2c=2

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

t^2 >= 100t +50

如果我开始输入tfrom 1, 2, 3, 4, 5, 6, 7, 8, 9, 10and 的值t^2 =100

在10，我还有

100,00 <= 100, 00 +50

在t=11, 和t^2 = 121, 我有以下

14,641 >= 12150.

所以我k会的11。

同样对于另一个方程，f(n) = 3n +8

g(n)将n。找c等k下面就是true。

c.g(n) >= f(n)

4n>=3n+8、舍弃常数8求c，将常数插8回方程中求k。

在k=8，我们有32>=32。