algorithm - 大 O 符号和渐近

Question

让

       d    
p(n) = Σ ai n^i 
      i=0

其中 ad > 0 是 n 的 d 次多项式，设 k 为常数。使用渐近符号的定义来证明以下性质。

a) if k >= d, then p(n) = O(n^k)

还有 4 个对应于 Omega、theta、small o 和 small omega 属性，但如果我能知道如何开始，我可以自己找出其他的。

Answer 1

这很简单。在此处查看 Big O Notation 正式定义:http://en.wikipedia.org/wiki/Big_o_notation#Formal_definition ，特别是在该部分末尾的公式中，limsup。您要证明的是，随着 n 趋于(正)无穷大，p(n)/n^k 的极限是一个实数。如果 k > d，则极限为零。如果k=d，那么极限就是a_d。为什么？因为它是 n^k 上的一个简单多项式(d 阶)，它也是一个多项式(k 阶)。查看计算多项式的极限。