渐近界与大O符号

Question

假设我们有两个单调递增的函数f和g，使得f(n)=Ω(n)且f(g(n))=O(n)，那么我想得出结论g(n)=O(n)。这种说法正确吗？

我认为这是一个错误的说法，我一直试图提供反例来证明这是错误的说法，但尝试了很多次后，我开始持不同看法。

请问，如果这是一个错误的说法，你能否提供一些解释或示例，或者如果这是一个正确的说法，是否有一种证明方法。

- david kokiashvili

Answer 1

我相信这个说法是正确的。以下是证明。

假设 f(n) = Ω(n)，这意味着存在常数 c，n₀，使得对于任何 n ≥ n₀，

f(n) ≥ cn. (1)

同样地，由于 f(g(n)) = O(n)，我们知道存在常数 d，n₁，使得对于任何 n ≥ n₁，

f(g(n)) ≤ dn. (2)

现在有两种情况。第一种情况是 g(n) = O(1)，在这种情况下我们完成了因为 g(n) 是 O(n)。第二种情况是 g(n) ≠ O(1)，在这种情况下 g 增长无限大。这意味着存在一个 n₂，使得 g(n₂) ≥ n₀（g 增长无限大，所以它最终超过了 n₀），且 n₂ ≥ n₁（只需选择一个大的 n₂）。

现在，选择任何 n ≥ n₂。由于 n ≥ n₂，我们有 g(n) ≥ g(n₂) ≥ n₀，因为 g 是单调递增的，因此根据（1），我们可以看到

f(g(n)) ≥ cg(n)。

由于 n ≥ n₂ ≥ n₁，我们可以将这个不等式与方程（2）结合起来，得到

dn ≥ f(g(n)) ≥ cg(n)。

因此，特别地，我们有

g(n) ≤ (d / c)n

对于所有 n ≥ n₂，因此 g(n) = O(n)。

- templatetypedef

---

非常感谢！ - david kokiashvili