algorithm - 寻找 f(n) 的上限

Question

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

案例 1:找到 f(n)=3n+8 的上限

很明显，当 n-> 无穷时，f(n)->3。所以 3n+8 应该小于或等于 4n 。所以我可以把 c​​ 当作 4。

case2:找到 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 <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.

检查 here for how to solve an inequality using wavy-curve method ，但要尝试此操作，您需要找到求解给定方程式的 n 值。