8

N^2がc2^Nによって制限されていることははっきりとわかりますが、big-Oの正式な定義を使用してそれを証明するにはどうすればよいですか。MIで簡単に証明できます

これが私の試みです。定義上、任意のn> n0に対して、f（n）<= Cg（n）である定数Cが存在します。ここでf（n）= n ^ 2およびg（n）= 2 ^ n

対数を両側に取り、Cを解く必要がありますか？

フィボナッチ数列についてもう1つ質問がありますが、漸化式を解きます。

int fib(int n){
   if(n<=1) return n;
   else return fib(n-1) + fib(n-2);

方程式は.. 

T(n) = T(n-1)+T(n-2)+C // where c is for the adding operation
それで
T(n) = T(n-2) + 2T(n-3) + T(n-4) + 3c

そしてもう1つ 

T(n) = T(n-3) + 3T(n-4) + 3T(n-5) + T(n-6) + 6c

それから私は一般的な方程式を形成するために迷子になり始めましたiパターンはどういうわけかパスカルの三角形のようなものですか？ 

 t(n) = t(n-i) + aT(n-i-1) + bT(n-i-2) + ... + kT(n-i-i) + C

4

3 に答える 3

8

ご指摘のとおり、f(x) ϵ O(g(x))かどうかを確認するには、見つける必要があります...

  • ...一部のc > 0および
  • ...いくつかのx 0

すべてのx > x 0に対してf(x) < c·g(x)となります。

この場合、 c = 1とx 0 = 2を選択できます。証明する必要があるのは、

    x 2 < 2 x for all x > 2

この時点で、両側のログを取ることができます (if log( x ) > log( y ), then x > y .) 基数 2 のログを使用していると仮定すると、次の結果が得られます。

    ログ(x 2 ) < ログ(2 x )

対数の標準的な法則により、次のようになります。

    2・log(x) < x・log(2)

log(2) = 1 なので、これは次のように記述できます。

    2·log(x) < x

x = 2 と設定すると、次のようになります。

    2·log(2) = 2

xはlog(x)よりも速く成長するため、 2·log(x) < xがすべてのx > 2に対して成り立つことがわかります。

于 2012-07-12T07:25:01.763 に答える