math - 求数学函数的上界(函数分析)

Question

我试图通过我拥有的一本书来理解 Big-O 表示法，它通过使用函数来涵盖 Big-O，尽管我有点困惑。这本书说 O(g(n)) 其中 g(n) 是 f(n) 的上限。所以我理解这意味着 g(n) 在较大的 n 值下给出了 f(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 的 Data Structures and Algorithms Made Easy

不确定这篇文章是属于这里还是属于数学板。

Answer 1

准备工作

首先，让我们松散地说明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) 的问题是退化的。事实上，如果存在任何这样的常数对，就会存在无数个不同的这样的常数对。

显示 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 )，我们可以证明它适用于无数种不同的常数选择(例如，它自然适用于 c=10 和 n0=20 ，...，等等)。