time-complexity - 成長の順番

Question

為に

f = n(log(n))^5
g = n^1.01

は

f = O(g)
f = 0(g)
f = Omega(g)?

両方を n で割ってみました。

f = log(n)^5
g = n^0.01

しかし、どちらがより速く成長するかはまだわかりません。誰かがこれについて私を助けて、答えの理由を説明できますか? どちらがより速く成長するかを（電卓なしで）どのように判断できるかを本当に知りたいです。

score 8 · Accepted Answer

対数プロファイルを比較するのがおそらく最も簡単です。

もし (ある C1, C2 に対して a>0)

f < C1 n log(n)^a
g < C2 n^(1+k)

次に (n が十分に大きい場合)

log(f) < log(n) + a log(log(n)) + log(C1)
log(g) < log(n) + k log(n) + log(C2)

どちらも log(n) の増加が支配的であるため、問題はどちらの残差が大きいかです。log(n) 残差は、k の小ささや a の大きさに関係なく、log(log(n)) よりも速く成長するため、g は f よりも速く成長します。

したがって、big-O 表記法に関しては、g は f よりも速く成長するため、f は (漸近的に) g のような関数によって上から制限することができます。

f(n) < C3 g(n)

したがって、f = O(g) です。同様に、g は f によって下から制限できるため、g = Omega(f) となります。しかし、f は g のような関数によって下から制限することはできません。したがって、f != オメガ(g) および f != シータ(g) です。

しかし、aaa は非常に良い点を示しています。n がひどく大きくなるまで、g は f を支配し始めません。

アルゴリズムのスケーリングについてはあまり経験がないので、修正を歓迎します。

score 3 · Accepted Answer

これをいくつかの簡単で再利用可能な補題に分割します。

補題 1: 正の定数 k の場合、f = O(g) は f = O(kg) の場合に限ります。

証明: f = O(g) とします。このとき |f(n)| を満たす定数 c と N が存在する。< c |g(n)| n > N の場合。したがって |f(n)| < (c/k) (k |g(n)| ) (n > N および定数 (c/k) の場合)、f = O (kg)。逆は自明に似ています。

補題 2: h が正の単調増加関数であり、十分に大きな n に対して f と g が正の場合、h(f) = O( h(g) ) の場合に限り、f = O(g) になります。

証明: f = O(g) とします。このとき |f(n)| を満たす定数 c と N が存在する。< c |g(n)| n > N の場合。n > M の場合、f と g は正であるため、n > max(N, M) の場合、f(n) < cg(n) です。h は単調増加するため、n > max(N, M) の場合、h(f(n)) < ch(g(n)) となり、最後に |h(f(n))| となります。< c |h(g(n))| h が正であるため、n > max(N, M) の場合。したがって、h(f) = O(h(g)) です。逆も同様です。重要な事実は、h が単調に増加する場合、h(a) < h(b) => a < b です。

補題 3: h が反転可能な単調増加関数の場合、f(h) + O(g(h)) の場合に限り、f = O(g) となります。

証明: f = O(g) とします。このとき |f(n)| を満たす定数 c, N が存在する。< c |g(n)| n > N の場合。したがって |f(h(n))| < c |g(h(n))| h(n) > N. h(n) は可逆で単調に増加するため、n > h^-1(N) の場合は常に h(n) > N です。したがって、h^-1(N) は必要な新しい定数であり、f(h(n)) = O(g(h(n)) です。g の逆を使用して、逆も同様に続きます。

補題 4: n > M に対して h(n) が非ゼロの場合、f = O(g) は、f(n)h(n) = O(g(n)h(n)) の場合に限ります。

補題 5a: log n = O(n)。

証明: f = log n、g = n とする。その場合、f' = 1/n および g' = 1 であるため、n > 1 の場合、g は f よりも速く増加します。また、g(1) = 1 > 0 = f(1) なので |f(n)| < |g(n)| n > 1 および f = O(g) の場合。

補題 5b: n != O(log n)。

証明: 矛盾のために別のことを仮定し、f = n および g = log n とする。次に、いくつかの定数 c、N、|n| について < c |ログ n| n > N の場合。

d = max(2, 2c, sqrt(N+1) ) とします。補題 5a の計算により、d > 2 > 1 であるため、log d < d となります。したがって |f(2d^2)| = 2d^2 > 2d(log d) >= d log d + d log 2 = d (log 2d) > 2c log 2d > c log (2d^2) = cg(2d^2) = c |g(2d ^2)| 2d^2 > N の場合、矛盾。したがって、f != O(g) です。

これで、最初に尋ねた質問に対する回答をまとめることができます。

ステップ1：

log n = O(n^a)
n^a != O(log n)

任意の正の定数 a.

証明: 補題 5a により log n = O(n)。したがって、補題 3 (h(n) = n^a の場合)、4、および 1 により、log n = 1/a log n^a = O(1/an^a) = O(n^a) となります。同様に、補題 5b を使用して次のことが成り立ちます。

ステップ2：

log^5 n = O(n^0.01)
n^0.01 != O(log^5 n)

証明: ステップ 1 で log n = O(n^0.002)。次に補題 2 (h(n) = n^5) により、log^5 n = O( (n^0.002)^5 ) = O(n ^0.01)。2 番目の事実も同様です。

最終的な答え:

n log^5 n = O(n^1.01)
n^1.01 != O(n log^5 n)

言い換えると、

f = O(g)
f != 0(g)
f != Omega(g)

証明: ステップ 2 に補題 4 (h(n) = n を使用) を適用します。

実践すれば、これらのルールは「自明」になり、第二の性質になります。そして、テストで答えを証明する必要がない限り、これらの種類の大きな問題を解決する必要があります。

score 2 · Accepted Answer

それらの交差点をチェックするのはどうですか？

Solve[Log[n] == n^(0.01/5), n]

                                       1809
{{n -> 2.72374}, {n -> 8.70811861815 10    }}

Mathematica でごまかした

導関数で推論することもできます

In[71]:= D[Log[n], n]

1
-
n
In[72]:= D[n^(0.01/5), n]

0.002
------
 0.998
n

n が非常に大きくなり、最初の変化がゼロになる傾向があり、後の関数が導関数を失わない (指数が 0 より大きい) 場合に何が起こるかを考えてみてください。

これにより、どちらが理論的により複雑かがわかります。ただし、実用的な領域では、最初の機能がより速く成長します。

score 0 · Accepted Answer

これは、ログについて何かを証明することなく、数学的に 100% コーシャではありませんが、次のように述べています。

f = log(n)^5
g = n^0.01

両方のログを取得します。

log(f) = log(log(n)^5)) = 5*log(log(n)) = O(log(log(n)))
log(g) = log(n^0.01) = 0.01*log(n) = O(log(n))

このことから、最初のログは漸近的にゆっくりと成長することがわかります。これは、2 つのログが含まれており、ログの成長が遅いためです。ログを取ることによるこの推論が有効である理由の非形式的な議論は次のとおりです。したがって、g の桁数が f の桁数よりも漸近的に速く増加している場合、実際の数 g は確実に数 f よりも速く増加しています!

time-complexity - 成長の順番

4 に答える 4

Related

Reference