已知f=O(g)、g=O(f)且f(n)>g(n)，判断f−g=O(1)是否成立

核心结论 #

该命题不成立，可通过反例证伪。

反例构造 #

构造如下满足所有题设条件的非负函数：

• 取 f(n) = 2n，g(n) = n，其中n为正整数

逐一验证前置条件：

1. 验证 f = O(g)：取常数c=2，对所有n≥1，有 0 < 2n ≤ 2·n = c·g(n)，符合大O符号定义
2. 验证 g = O(f)：取常数c₂=1，对所有n≥1，有 0 < n ≤ 1·2n = c₂·f(n)，符合大O符号定义
3. 验证大小关系：对任意正整数n，f(n) = 2n > n = g(n)，满足题设要求

计算二者差值可得 f(n) - g(n) = n，该函数随n增长无界，不存在常数C和n₀使得对所有n≥n₀都有 n ≤ C，因此 f - g ≠ O(1)，原命题不成立。

原理说明 #

你无法通过大O定义推导出差值特性的核心原因是：大O符号描述的是函数的相对增长速率，仅约束两个函数的比值有界，不约束二者的绝对差值。只要两个函数的比值始终落在正的上下界区间内，就满足 f = Θ(g)（即同时满足 f = O(g) 和 g = O(f)），但二者的绝对差值完全可以随n无限增长，没有固定上限。

你也可以构造其他同类反例验证，比如 f(n) = n² + n、g(n) = n²，二者差值为n，同样不满足O(1)要求。

内容的提问来源于stack exchange，提问作者Ni Jiasheng