f（n）= log（n）^ mはすべての自然数mに対してO（n）

Question

TAはこれが今日は真実だと言ったが、私はグーグルでこれを確認することができなかった。これはlog（n）^ 2、log（n）^ 3、...、log（n）^ mのような関数がすべてO（n）であるということです。

これは本当ですか？

Answer 1

任意の自然数m > 2（m ∈ ℕ+）のための、請求項

機能f(n) = log(n)^mは、 O(n)です。

I.e.そこに正の定数のセットが存在cとn0ように こと以下が成り立つ：

log(n)^m < c · n, for all n > n0, { m > 2 | m ∈ ℕ+ }  (+) 

---

証明を

• は(+)がないホールドを行うと仮定し、この仮定をとする。

即ち、(*)与えられ、いかなる正の定数の組cと(+)はm > 2の任意の値について成り立つことn0ようには存在しません。この仮定の下で、以下はすべて正の定数cとn0ためは、n > n0よう（感謝@Oriol）が存在することを、保持している：今

log(n)^m ≥ c · n, { m > 2 | m ∈ ℕ+ }      (++) 

、(++)が保持している場合、その後、(++)における不平等がします不等式の両側に単調に増加する関数を適用した後も保持する。そのような機能は(++)が成立し、その後、すべての正の定数cとn0ためは、以下がを保持するようn > n0が存在するという仮定の下で、便利に、log関数自体したがって

あります

log(log(n)^m) ≥ log(c · n), { m > 2 | m ∈ ℕ+ } 

m · log(log(n)) ≥ log(c · n), { m > 2 | m ∈ ℕ+ }   (+++) 

しかし、(+++)は矛盾が明らかである：0上log(n)優勢（WRT成長）ので、

我々缶ためm > 2 -alwaysの任意の値が定数cのセットと(+++)（したがって(++)）は全てn > n0ために破られるようにn0を見つけます。

したがって、仮定(*)は矛盾によって偽であることが証明されているため、(+)が成り立ちます。

=>f(n) = log(n)^mのために、任意の有限整数m > 2のために、それはそのf ∈ O(n)を保持しています。

Answer 2

はい。関数がf(n)なら、mはパラメータであり、fはそれに依存しないことを意味します。実際には、それぞれmの異なるf_m関数があります。

f_m(n) = log(n)^m 

次に簡単です。 m ∈ ℕを考えると、repeatively

 f_m(n)   log(n)^m   m * log(n)^(m-1) 
limsup ──────── = limsup ────────── = limsup ────────────────── = 
n→∞  n  n→∞  n   n→∞   n 

      m*(m-1) * log(n)^(m-2)    m! 
= limsup ──────────────────────── = … = limsup ──── = 0 
       n      n→∞ n 

したがって、f_m ∈ O(n)L'Hôpital's ruleを使用しています。

もちろん、私たちがf(m,n) = log(n)^mだったら違うでしょう。例えば、多くの点でm=n、

 f(n,n)   log(n)^n 
limsup ──────── = limsup ────────── = ∞ 
n→∞  n  n→∞  n 

その後f ∉ O(n)

Answer 3

を取って、任意の正の整数mのために我々が持っていることがより直感的です：

x^m = O(e^x) 

これは、指数関数的成長は、多項式の成長を支配することを言います（なぜ指数関数時間アルゴリズムがコンピュータプログラミングの悪いニュースなのか）。

最後に

log(n)^m = O(e^log(n)) = O(n) 

、ため以降：単にx = log(n)を取り、その後xがnが無限大になる傾向とe^xとlog(x)が逆であることを場合に限り、無限に傾向があるという事実を使用し、これが真実であると仮定すると

任意の自然数m、ルート機能n => n^(1/m)が増加している、我々は

log(n) = O(n^(1/m)) 

Tとして結果を書き換えることができます彼の書き方では、log(n)はnのどのルート（正方形、立方体など）よりも遅く成長し、より明らかにe^nに対応します。編集し

---

：上記log(n)^m = O(n)はx^m = O(e^x)より身近から続くことを示しました。それをより自己完結型の証明に変換するには、後でそれを直接的に表示することができます。 e^xのためのテイラーシリーズと

スタート：

e^x = 1 + x/1! + x^2/2! + x^3/3! + ... + x^n/n! + ... 

これはすべての実数xのために収束することが知られています。正の整数mが指定されている場合は、K = (m+1)!とします。その後、x > K場合我々はそれゆえx^m = O(e^x)を意味

x^m = x^(m+1)/x < x^(m+1)/(m+1)! < e^x 

、1/x < 1/(m+1)!を持っています。 （e^xの展開のすべての用語は、x>0とx^(m+1)/(m+1)!がこれらの用語のうちの1つに過ぎないと厳密に正であるため、上記の最後の不等式は真です）。