多项式的 θ符号-基本算法

Question

下面函数的Theta符号是什么?

f(n) = (n + 1)/(n^2 + 2)

任何建议都会很棒!!

Answer 1

对于较大的n值(n → ∞)，表达式渐近等价于1/n

为了验证f(n)与g(n)相等，我们必须证明它们的比值极限是常数:

f(n) / (1/n)  = n*(n+1)/(n^2 + 2) = (n^2 + n)/(n^2 + 2) = 
n^2/(n^2 + 2) + n/(n^2 + 2) = 
(n^2 + 2)/(n^2 + 2) - 2/(n^2 + 2) + n/(n^2 + 2) = 
1  - 2/(n^2 + 2) + n/(n^2 + 2)

limit(f(n)/(1/n))[n → ∞] = 1 - 0 + 0 = 1

和f(n)渐近等价于1/n