多项式Theta记号求解：求函数f(n)=(n+1)/(n²+2)的Theta表示

结论 #

给定函数 f(n) = (n + 1)/(n² + 2)，对应的Theta记号为 Θ(1/n)。

推导思路 #

核心定义回顾 #

Theta记号用来表示函数的紧渐近界：如果存在正的常数c₁、c₂和正整数n₀，使得对所有n ≥ n₀，都满足 c₁·g(n) ≤ f(n) ≤ c₂·g(n)，则可判定 f(n) = Θ(g(n))。

分步放缩验证 #

我们对f(n)的分子分母分别做合理放缩（取n₀ = 1，即所有n≥1的场景）：

• 上界推导：
  分子：n + 1 ≤ n + n = 2n
  分母：n² + 2 ≥ n²
  因此 f(n) ≤ 2n / n² = 2·(1/n)，可得上界常数c₂ = 2
• 下界推导：
  分子：n + 1 ≥ n
  分母：n² + 2 ≤ n² + 2n² = 3n²（n≥1时2 ≤ 2n²恒成立）
  因此 f(n) ≥ n / 3n² = (1/3)·(1/n)，可得下界常数c₁ = 1/3

综上，当n≥1时，(1/3)·(1/n) ≤ f(n) ≤ 2·(1/n)，完全符合Theta紧界的定义，因此结论成立。

通用解题建议 #

• 对于多项式构成的分式函数做渐近分析时，仅需保留分子和分母的最高次项即可快速判断量级：本题分子最高次为1次的n，分母最高次为2次的n²，整体量级为n¹/n² = n⁻¹ = 1/n，和推导结果一致
• 放缩时要注意选择的常数和n₀必须对所有大于等于n₀的n都成立，不能只满足少数小n的场景
• 可以代入较大的n值做初步验证，比如n=1000时f(n)≈0.001，和1/n的结果几乎相等，可快速排除错误的量级判断

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