Биг-О нотация и асимптотика

Question

Пусть

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

, где ad> 0 - многочлен степени d от n, и пусть 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. То, что вы пытаетесь доказать, это то, что предел p (n) / n ^ k, когда n переходит в (положительную) бесконечность, является действительным числом. Если k> d, предел равен нулю. Если k = d, то предел равен a_d. Зачем? Потому что это простой многочлен (порядка d) над n ^ k, который также является многочленом (порядка 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 действительно делает утверждение действительным.