寻找数学函数的上界（函数分析）
Finding the upper bound of a mathematical function (function analysis)
我正在尝试通过我拥有的一本书来理解 Big-O 符号，它通过使用函数来涵盖 Big-O，尽管我有点困惑。书上说 O(g(n)) 其中 g(n) 是 f(n) 的上限。所以我明白这意味着 g(n) 给出了 f(n) 在更大的 n 值下的最大增长率。
并且存在一个 n_0，其中 cg(n)（其中 c 是某个常数）和 f(n) 的增长率具有相同的增长率。
但我感到困惑的是这些关于在数学函数中寻找大 O 的例子。
这本书说找到 f(n) = n^4 +100n^2 + 50 的上限
然后他们说 n^4 +100n^2 + 50 <= 2n^4 （不确定为什么是 2n^4）
然后他们找到了 n_0 =11 和 c = 2，我明白为什么大 O 是 O(n^4) 但我只是对其余部分感到困惑。
这一切都令人沮丧，因为我不明白，但我觉得这是一个我必须理解的重要话题。
如果有人好奇，这本书是 Narasimha Karumanchi 的《数据结构和算法变得简单》
不确定这个 post 属于这里还是属于数学板。
准备工作
首先，让我们粗略地说明 f 在 O(g(n)) 中的定义（注意：O(g(n)) 是一个 函数集 ，所以为了挑剔，我们说 f 在 O(...) 中，而不是 f(n) 在 O(...) 中）。
If a function f(n) is in O(g(n)), then c · g(n) is an upper bound on
f(n), for some constant c such that f(n) is always ≤ c · g(n),
for large enough n (i.e. , n ≥ n0 for some constant n0).
因此，为了证明f(n)在O(g(n))中，我们需要找到一组满足
的常数(c, n0)
f(n) < c · g(n), for all n ≥ n0, (+)
但是这个集合不是唯一的。即，找到使 (+) 成立的常数 (c, n0) 的问题是 degenerate。事实上，如果存在任何这样的常数对，就会存在无数个不同的这样的常数对。
显示 f ∈ O(n^4)
现在，让我们继续看看让您感到困惑的例子
Find an upper asymptotic bound for the function
f(n) = n^4 + 100n^2 + 50 (*)
一种直接的方法是用高阶项表示 (*) 中的低阶项，特别是 w.r.t。界限 (... < ...).
因此，我们看看是否可以在 n 上找到下界，使得以下内容成立
100n^2 + 50 ≤ n^4, for all n ≥ ???, (i)
通过求解方程
，我们可以很容易地找到 (i) 中等式成立的时间
m = n^2, m > 0
m^2 - 100m - 50 = 0
(m - 50)^2 - 50^2 - 50 = 0
(m - 50)^2 = 2550
m = 50 ± sqrt(2550) = { m > 0, single root } ≈ 100.5
=> n ≈ { n > 0 } ≈ 10.025
因此，(i) 对 n ≳ 10.025 成立，但我们更愿意在 n 上用一个整洁的整数值表示这个界限，因此四舍五入到 11 :
100n^2 + 50 ≤ n^4, for all n ≥ 11, (ii)
从 (ii) 可以看出以下内容成立
f(n) = n^4 + 100n^2 + 50 ≤ n^4 + n^4 = 2 · n^4, for all n ≥ 11, (iii)
而这种关系恰好是 (+) 与 c = 2、n0 = 11 和 g(n) = n^4，因此我们证明了 f ∈ O(n^4)。但是，请再次注意，常量 c 和 n0 的选择是 方便 之一，这不是唯一的。由于我们已经证明 (+) 对一组常数 (c,n0 成立），我们可以证明它对无限量的不同此类常数选择成立（例如，它自然地对 [=43 成立） =] 和 n0=20, ..., 等等）。
我正在尝试通过我拥有的一本书来理解 Big-O 符号，它通过使用函数来涵盖 Big-O，尽管我有点困惑。书上说 O(g(n)) 其中 g(n) 是 f(n) 的上限。所以我明白这意味着 g(n) 给出了 f(n) 在更大的 n 值下的最大增长率。
并且存在一个 n_0，其中 cg(n)（其中 c 是某个常数）和 f(n) 的增长率具有相同的增长率。
但我感到困惑的是这些关于在数学函数中寻找大 O 的例子。
这本书说找到 f(n) = n^4 +100n^2 + 50 的上限 然后他们说 n^4 +100n^2 + 50 <= 2n^4 （不确定为什么是 2n^4） 然后他们找到了 n_0 =11 和 c = 2，我明白为什么大 O 是 O(n^4) 但我只是对其余部分感到困惑。
这一切都令人沮丧，因为我不明白，但我觉得这是一个我必须理解的重要话题。
如果有人好奇，这本书是 Narasimha Karumanchi 的《数据结构和算法变得简单》
不确定这个 post 属于这里还是属于数学板。
准备工作
首先，让我们粗略地说明 f 在 O(g(n)) 中的定义（注意：O(g(n)) 是一个 函数集 ，所以为了挑剔，我们说 f 在 O(...) 中，而不是 f(n) 在 O(...) 中）。
If a function f(n) is in O(g(n)), then c · g(n) is an upper bound on f(n), for some constant c such that f(n) is always ≤ c · g(n), for large enough n (i.e. , n ≥ n0 for some constant n0).
因此，为了证明f(n)在O(g(n))中，我们需要找到一组满足
f(n) < c · g(n), for all n ≥ n0, (+)
但是这个集合不是唯一的。即，找到使 (+) 成立的常数 (c, n0) 的问题是 degenerate。事实上，如果存在任何这样的常数对，就会存在无数个不同的这样的常数对。
显示 f ∈ O(n^4)
现在，让我们继续看看让您感到困惑的例子
Find an upper asymptotic bound for the function
f(n) = n^4 + 100n^2 + 50 (*)
一种直接的方法是用高阶项表示 (*) 中的低阶项，特别是 w.r.t。界限 (... < ...).
因此，我们看看是否可以在 n 上找到下界，使得以下内容成立
100n^2 + 50 ≤ n^4, for all n ≥ ???, (i)
通过求解方程
，我们可以很容易地找到 (i) 中等式成立的时间m = n^2, m > 0
m^2 - 100m - 50 = 0
(m - 50)^2 - 50^2 - 50 = 0
(m - 50)^2 = 2550
m = 50 ± sqrt(2550) = { m > 0, single root } ≈ 100.5
=> n ≈ { n > 0 } ≈ 10.025
因此，(i) 对 n ≳ 10.025 成立，但我们更愿意在 n 上用一个整洁的整数值表示这个界限，因此四舍五入到 11 :
100n^2 + 50 ≤ n^4, for all n ≥ 11, (ii)
从 (ii) 可以看出以下内容成立
f(n) = n^4 + 100n^2 + 50 ≤ n^4 + n^4 = 2 · n^4, for all n ≥ 11, (iii)
而这种关系恰好是 (+) 与 c = 2、n0 = 11 和 g(n) = n^4，因此我们证明了 f ∈ O(n^4)。但是，请再次注意，常量 c 和 n0 的选择是 方便 之一，这不是唯一的。由于我们已经证明 (+) 对一组常数 (c,n0 成立），我们可以证明它对无限量的不同此类常数选择成立（例如，它自然地对 [=43 成立） =] 和 n0=20, ..., 等等）。