math - 渐近界和大 O 符号

Question

假设我们有两个单调递增的函数 f,g 使得 f(n)=Ω(n) 和 f(g(n))=O(n) 是否正确？那么我想得出的结论是g(n)=O(n)。

我认为这是一个错误的说法，我一直在尝试提供反例来证明这是错误的说法，但经过多次尝试后，我开始不这么认为。

如果这是一个错误的说法或证明它是否正确的方法，您能否提供某种解释或示例。

Answer 1

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

假设 f(n) = Ω(n)。这意味着存在常数 c, n₀ 这样

f(n) ≥ cn for any n ≥ n₀. (1)

类似地，由于 f(g(n)) = O(n)，我们知道存在常数 d, n₁ 使得

f(g(n)) ≤ dn for any n ≥ n₁. (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)。