TAはこれが今日は真実だと言ったが、私はグーグルでこれを確認することができなかった。これはlog(n)^ 2、log(n)^ 3、...、log(n)^ mのような関数がすべてO(n)であるということです。f(n)= log(n)^ mはすべての自然数mに対してO(n)
これは本当ですか?
TAはこれが今日は真実だと言ったが、私はグーグルでこれを確認することができなかった。これはlog(n)^ 2、log(n)^ 3、...、log(n)^ mのような関数がすべてO(n)であるということです。f(n)= log(n)^ mはすべての自然数mに対してO(n)
これは本当ですか?
任意の自然数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)
を保持しています。
(+)の否定は、すべての正の定数cとn0に対して、log(n)^ m≥c・nとなるn> n0が存在すると考えます。あなたの答えは 'すべてのn> n0'です。 – Oriol
@dfriありがとう!!! – TheSalamander
@ TheSalamanderがお手伝いします。 – dfri
はい。関数が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)
を取って、任意の正の整数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つに過ぎないと厳密に正であるため、上記の最後の不等式は真です)。
それは私にはすぐわかりませんが証明する。 – MooseBoys