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 つありますが、開始方法がわかれば、他のプロパティを自分で見つけ出すことができます。

Answer 1

とてもシンプルです。http://en.wikipedia.org/wiki/Big_o_notation#Formal_definitionの Big O Notation の正式な定義を参照してください。特に、セクションの最後にある式を参照して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 のこの選択が実際にステートメントを有効にすることを帰納法によって実際に証明することができます。