algorithm - Big-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

这很简单。在此处查看大 O 表示法的正式定义：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 阶）。看看计算多项式的极限。

Answer 2

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

如果这是真的，那么存在 N、A 和 B 使得：

p(n) <= A + B*n^k

对于所有 n >= N

这样的 N、A 和 B 存在，例如：

     d    
 B = Σ ai n^i 
    i=0


 A = 1
 N = 1

如果您认为这足够有洞察力，或者实际上通过归纳证明 N、A 和 B 的选择确实使该陈述有效，您可以将其保留。