渐近界和大 O 符号
Asymptotic bounds and Big O notation
假设我们有两个单调递增的函数f，g使得f(n)=Ω(n)和f(g(n))=O(n)，这样说对吗？然后我想得出结论 g(n)=O(n).
我认为这是一个错误的说法，我一直在尝试提供反例来证明这是一个错误的说法，但经过多次尝试后，我开始不这么认为了。
如果这是一个错误的说法或证明它是否正确的方法，您能否提供某种解释或示例。
我相信这个说法是正确的。这里有一个证明。
假设f(n) = Ω(n)。这意味着存在常数 c, n0 这样
f(n) ≥ cn for any n ≥ n0. (1)
类似地，由于f(g(n)) = O(n)，我们知道存在常数d，n1使得
f(g(n)) ≤ dn for any n ≥ n1. (2)
现在，有两个选择。第一个是 g(n) = O(1)，在这种情况下我们就完成了，因为 g(n) 那么 O(n)。第二种情况是 g(n) ≠ O(1)，在这种情况下 g 无限增长。这意味着存在一个 n2 使得 g(n2) ≥ n0 (g无限增长，所以它最终超过了 n0) 和 n2 ≥ n1 （只需选择一个大 n2).
现在，选择任意 n ≥ n2。由于 n ≥ n2，我们有 g(n) ≥ g(n2) ≥ n0 因为 g 是单调递增的，因此通过 (1) 我们看到
f(g(n)) ≥ cg(n).
由于n≥n2≥n1，我们可以将此不等式与式（2）结合得
dn ≥ f(g(n)) ≥ cg(n).
所以，特别是，我们有
g(n) ≤ (d / c)n
对于所有 n ≥ n2，所以 g(n) = O(n)。
假设我们有两个单调递增的函数f，g使得f(n)=Ω(n)和f(g(n))=O(n)，这样说对吗？然后我想得出结论 g(n)=O(n).
我认为这是一个错误的说法，我一直在尝试提供反例来证明这是一个错误的说法，但经过多次尝试后，我开始不这么认为了。
如果这是一个错误的说法或证明它是否正确的方法，您能否提供某种解释或示例。
我相信这个说法是正确的。这里有一个证明。
假设f(n) = Ω(n)。这意味着存在常数 c, n0 这样
f(n) ≥ cn for any n ≥ n0. (1)
类似地，由于f(g(n)) = O(n)，我们知道存在常数d，n1使得
f(g(n)) ≤ dn for any n ≥ n1. (2)
现在，有两个选择。第一个是 g(n) = O(1)，在这种情况下我们就完成了，因为 g(n) 那么 O(n)。第二种情况是 g(n) ≠ O(1)，在这种情况下 g 无限增长。这意味着存在一个 n2 使得 g(n2) ≥ n0 (g无限增长，所以它最终超过了 n0) 和 n2 ≥ n1 （只需选择一个大 n2).
现在，选择任意 n ≥ n2。由于 n ≥ n2，我们有 g(n) ≥ g(n2) ≥ n0 因为 g 是单调递增的，因此通过 (1) 我们看到
f(g(n)) ≥ cg(n).
由于n≥n2≥n1，我们可以将此不等式与式（2）结合得
dn ≥ f(g(n)) ≥ cg(n).
所以，特别是，我们有
g(n) ≤ (d / c)n
对于所有 n ≥ n2，所以 g(n) = O(n)。