求f(n)的上界

Question

我试图从基础上理解编程的概念。我遇到了两个例子。

case1:找上界的f (n) = 3 n + 8

很明显，当n>无穷大时f(n)->3。所以3n+8应该小于等于4n。所以c = 4

例2:找上界的f (n) = n ^ 4 + 100 (n ^ 2) + 50

对于所有n = 11, f(n)应该小于2(n^4)。他们是怎么得出n=11的?我明白替代不是更好的办法。

如果有人能解释一下求上界的过程，那就太好了。

Answer 1

这是一种检查方法，即通过替换或点击试用的方法。

他们检查了n^4 +100(n^2)+50 <2*(n^4)。>

或者换句话说，n^4 > (100 * n^2 + 50)。

当你解它的时候，结果会是11。

也就是说，对于n>= 11。n^4 +100(n^2)+50 & lt;2*(n^4) .

这个不容易计算，你可以用Wolfram Alpha搜索。

也可以通过求解n值的不等式来求解。

n^4 > (100 * n^2 + 50)
n^4 - 100 * n^2 - 50 > 0
// find the roots for this equation and then 
// you'll be easily able to deduce the value of n using wavy-curve method.

查看此处如何使用波浪曲线法求解不等式，但要尝试此方法，您需要找到解决给定方程的n值。