比较函数的边界
Comparing the Bounds of Functions
我理解函数边界的一般概念；例如，如果我们说一个函数
ƒ1(n) ∈ Ω(n^2)
那么我们知道ƒ1(n)是下界n^2约束内的元素，意思是ƒ1(n) 可以是任何增长较慢或等于 n^2 的函数。
现在，当我们谈论关于 ƒ1(n) 边界的其他函数时，我开始感到困惑。例如，假设我们有一个声明如下：
If
ƒ1(n) ∈ Ω(n^2)
And
ƒ2(n) ∈ Θ(n)
Then
ƒ2(n) ∈ O(ƒ1(n))
真假难辨。我有两种相互矛盾的不同方法：
- true - 因为 ƒ2 在 n[ 下紧密绑定=49=]，它可以被认为是 O(ƒ1(n)) 约束内的元素，因为 ƒ2 不会比 ƒ1。
- false - 因为 ƒ1 的下限为 n ^2，函数ƒ2，在n下紧密绑定，不能被认为是[的上界元素=24=]ƒ1 因为我们知道 ƒ1 不会有比 n^2 增长慢的上限。
我想到的这两种方法对我来说似乎都有效；我想当我们试图决定另一个函数是否是其上限的元素时，我是否关心 ƒ1 的下限感到困惑。
如能帮助澄清这一点，我们将不胜感激。
让我们看看big-O等的定义。所有公式都适用于足够大的n。然后，存在一些常量k，例如：
第一个公式：
ƒ1(n) ∈ Ω(n^2)
⇔ k1 * n^2 <= f1(n)
第二个公式：
ƒ2(n) ∈ Θ(n)
⇔ k2 * n <= f2(n) <= k3 * n
我们知道 k3 * n < k1 * n^2（同样，对于足够大的 n）。因此：
k2 * n <= f2(n) <= k3 * n < k1 * n^2 <= f1(n)
这可以减少到
f2(n) < f1(n)
根据这些知识，我们看到推断的公式是正确的：
ƒ2(n) ∈ O(ƒ1(n))
⇔ f2(n) <= k4 * f1(n)
我理解函数边界的一般概念；例如，如果我们说一个函数
ƒ1(n) ∈ Ω(n^2)
那么我们知道ƒ1(n)是下界n^2约束内的元素，意思是ƒ1(n) 可以是任何增长较慢或等于 n^2 的函数。
现在，当我们谈论关于 ƒ1(n) 边界的其他函数时，我开始感到困惑。例如，假设我们有一个声明如下：
If
ƒ1(n) ∈ Ω(n^2)
And
ƒ2(n) ∈ Θ(n)
Then
ƒ2(n) ∈ O(ƒ1(n))
真假难辨。我有两种相互矛盾的不同方法：
- true - 因为 ƒ2 在 n[ 下紧密绑定=49=]，它可以被认为是 O(ƒ1(n)) 约束内的元素，因为 ƒ2 不会比 ƒ1。
- false - 因为 ƒ1 的下限为 n ^2，函数ƒ2，在n下紧密绑定，不能被认为是[的上界元素=24=]ƒ1 因为我们知道 ƒ1 不会有比 n^2 增长慢的上限。
我想到的这两种方法对我来说似乎都有效；我想当我们试图决定另一个函数是否是其上限的元素时，我是否关心 ƒ1 的下限感到困惑。
如能帮助澄清这一点，我们将不胜感激。
让我们看看big-O等的定义。所有公式都适用于足够大的n。然后，存在一些常量k，例如：
第一个公式：
ƒ1(n) ∈ Ω(n^2)
⇔ k1 * n^2 <= f1(n)
第二个公式：
ƒ2(n) ∈ Θ(n)
⇔ k2 * n <= f2(n) <= k3 * n
我们知道 k3 * n < k1 * n^2（同样，对于足够大的 n）。因此：
k2 * n <= f2(n) <= k3 * n < k1 * n^2 <= f1(n)
这可以减少到
f2(n) < f1(n)
根据这些知识，我们看到推断的公式是正确的：
ƒ2(n) ∈ O(ƒ1(n))
⇔ f2(n) <= k4 * f1(n)