多项式的 Theta 表示法 - 基本算法 [英] Theta notation for polynomial - Fundamental Algorithms

问题描述

以下函数的 Theta 表示法是什么:

What is the Theta notation for the below function:

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

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

任何建议都会很棒！！！

Any suggestion would be great!!!

推荐答案

这个用于大 n 值的表达式 (n → ∞) 渐近等价于 1/n

This expression for large n values (n → ∞) is asymptotically equivalent to 1/n

要检查 f(n) 是否等价于 g(n)，我们必须证明它们的比率的极限是恒定的:

To check that f(n) is equivalent to g(n), we have to show that limit of their ratio is constant:

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 表示法 - 基本算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！