时间复杂度关系验证：O、θ复杂度下函数比值的复杂度判定

让我们逐个拆解这两个关于渐近复杂度的陈述：

陈述1：若f(n) = O(g(n))，则f(n)/g(n) = O(1) #

这个陈述不一定成立，具体取决于我们讨论的函数范围和O符号的定义：

• 在算法分析最常用的场景里（f(n)、g(n)都是非负函数，且当n足够大时g(n) > 0），这个陈述是成立的。根据O(g(n))的定义，存在常数C>0和n₀，当n≥n₀时，0 ≤ f(n) ≤ C·g(n)。两边除以正数g(n)，得到0 ≤ f(n)/g(n) ≤ C，这完全符合O(1)的定义——函数被一个常数上界约束。

• 但如果允许函数取负值，这个陈述就不成立。举个简单的反例：
  令f(n) = -n²，g(n) = -n。根据O符号的定义（f(n) ≤ C·g(n) 对足够大的n成立），取C=1，当n≥1时，-n² ≤ -n 等价于n² ≥n，显然成立，所以f(n) = O(g(n))。但计算比值：f(n)/g(n) = (-n²)/(-n) = n，这个函数的绝对值会随着n增大趋向无穷，根本无法被一个常数约束，因此f(n)/g(n) ≠ O(1)。

陈述2：若f(n) = Θ(g(n))，则f(n)/g(n) = Θ(1) #

这个陈述完全成立，只要当n足够大时g(n)≠0（否则除法无意义）。

根据Θ(g(n))的核心定义：存在正的常数C₁、C₂和n₀，当n≥n₀时，C₁·|g(n)| ≤ |f(n)| ≤ C₂·|g(n)|。由于n≥n₀时g(n)≠0，我们可以将不等式三边同时除以|g(n)|，得到：
C₁ ≤ |f(n)/g(n)| ≤ C₂

这正好匹配Θ(1)的定义：函数的绝对值被两个正常数分别下界和上界约束，所以f(n)/g(n) = Θ(1)是确凿无疑的。

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