algorithm - 与えられた関数が o(N) に等しいことを証明する

Question

私は、任意の定数 , (N の小さな O) に対してそれを証明しようとしていkますlog^k N = o(N)。

小さな o について私が知っているのは、よりも遅い速度T(n) = o(p(n))で成長する形に従うということだけです。また、何が何なのか分からないので、制限して使用することは本当にできません。誰かが私を始めるのを手伝ってくれませんか!T(n)p(n)L'hopital rulef(n)g(n)

Answer 1

あなたはそれを示す必要があります

    lim        (log^k N)/N  = 0
N -> infinity

書くN = e^xと、

lim (x^k)/(e^x) = 0

ここで、指数関数のべき級数展開を使用します。

e^x = ∑ (x^n)/n!

その商の見積もりを取得します。

ネタバレ：n = k+1givese^x > x^(k+1)/(k+1)!を使用して用語を選択すると、簡単に次のようになります(x^k)/(e^x) < (k+1)!/x。