math - nであることを証明してください！任意の定数自然数 p に対して O(n^p) に含まれない

Question

n! であることをどのように証明できますか? 任意の定数自然数 p に対して O(n^p) に含まれていませんか? また、(nk)(n choose k) は O(n^p) で、すべての k に対して?

Answer 1

スターリングの近似は、

log (n!) = n log n - n + O(log n) = O(n log n)

しかし

log (n^p) = p log n = O(log n)

一定のためp。よりも明らかにn!速く成長するn^pため、そうではありませんO(n^p)。

Answer 2

n! であることを証明できます。任意の定数自然数 p に対して O(n^p) にはありません。これは、(固定定数 p に対して) n をいつでも選択できることを示すことで、n! > n^p.

(アイデアを得るために、p のいくつかの低い値を選び、n! を n^p に対してプロットします)

2番目の部分の推論は同じ行に従います。バインド (n は k を選択) してから、最初の部分を使用します。

ヒント：カサブランカが指摘したように、スターリングの近似を使用できます

Answer 3

編集 (2011 年 3 月) - 簡単な微積分のみを使用した簡単な方法

O(n!) が O(n^p) と等しくないことを示す 1 つの方法は、n! の対数を比較することです。n^p の対数で。

ln(n!) = sum(ln(i)) {i: 1 ～ n}

ln(n^p) = p*ln(n)

ログの合計がどうなるかわからないため、これは役に立たないようです。トリックは、1 から n までの ln(i)di の積分を使用して下限を計算することです。

これは、下の画像で、黒の ln(x) が青の合計ステップ関数よりも小さいことがわかります。

ln(i)di の不定積分が i*ln(i) - i + C であるとすると、1 から n までを積分して次を得ることができます。

n*ln(n) - 下限として n + 1。

また、可能なすべての n よりも大きい p を選択することはできないため、次のようになります。

O(p ln(n)) < O(n ln(n))、O(n^p) < O(n!)

注: ln(n) を積分して ln(n!) の近似値を取得することは、スターリングの近似値の基礎です。これはより大まかな概算であり、逆対数を取ることによってそれを続けると: n! >= e*(n/e)^n ですが、スターリングでは e の代わりに sqrt(2*pi*n) があります。

1 から n+1 まで積分すると上限が得られます (合計ステップ関数は ln(n) のグラフ内に収まります)。