algorithm - アルゴリズム分析のレート？

Question

対数がどの多項式よりも遅くなるのはなぜですか？これの（理解できる）証拠は何ですか？

同様に、

指数が常にどの多項式よりも速く成長するのはなぜですか？

score 3 · Accepted Answer

編集：この答えは本質的にPengOneが言ったことをやっています。

私たちは限界を取ります

log_2(x) / x^p

定数p>0の場合、制限がゼロであることを示します。xが無制限に成長すると、log_2（x）とx ^ pの両方が無限大になるため、l'Hopitalのルールを適用します。これは、私たちの制限がの制限と同じであることを意味します

1/(x*ln2) / p*x^(p-1)

分数の単純なルールを使用して、これを次のように減らします

1 / (p * x^p * ln2)

分子が一定のときに分母が無限大になるので、限界を評価できます。これはゼロです。つまり、pの（正の）値に関係なく、log_2（x）はx^pよりも漸近的にゆっくりと成長します。

EDIT2：

ちなみに、この質問と投稿された回答に興味がある場合は、このリンクをたどって移動にコミットすることにより、新しいComputerScienceStackExchangeサイトのサポートを示すことを検討してください。

score 1 · Accepted Answer

2つの（非負の）実数値関数fとが与えられgた場合、次のように計算します

lim_{x -> infinity} f(x) / g(x)

この制限は次のとおりです。

これで、好きな例を取り上げて制限を計算し、どちらが速く成長するかを確認できます。

score 0 · Accepted Answer

あなたは派生物を考えることができます。

d（x ^ n）/ dx = nx ^（n-1）

d（ln x）/ dx = 1 / x

n> = 1の場合、nx ^（n-1）はxとともに増加するか、同じままですが、1 / xはxとともに減少するため、多項式はより速く成長します。

e ^ xの対数はxですが、n^xの対数はnlnxであるため、上記の引数を使用してe^xの対数とx^nの対数を比較すると、e^xの成長が速くなります。

3 に答える 3