algorithm - 比较函数的边界

Question

我理解函数边界的一般概念；例如，如果我们说一个函数

ƒ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 紧紧束缚，它可以被认为是约束内的元素O(ƒ1(n)) 因为 ƒ2 的生长速度并不比 ƒ1 慢。
• false - 由于 ƒ1 的下界为 n^2，函数 ƒ2 在 n 下紧密结合，不能被视为 ƒ1 上限的元素，因为我们知道 ƒ1 不会有一个增长速度比 n^2 慢的上限。

我想到的这两种方法对我来说似乎都有效；我想当我们试图确定另一个函数是否是其上限的元素时，我对我们是否关心 ƒ1 的下限感到困惑。

如果您能帮助澄清这一点，我们将不胜感激。

Answer 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)