algorithm - 寻找 af(n) 的上限

Question

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

case1: 求 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.

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