多项式的 Theta 表示法 - 基础算法

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

多项式的 Theta 表示法 - 基础算法

Theta notation for polynomial - Fundamental Algorithms

algorithm

big-o