だから、明らかに、log(n)ですO(n)。しかし、どう(log(n))^2ですか？何についてですか、sqrt(n)または—何が何log(n)を制限していますか?
次のような比較のファミリーがあります。
nᵃ (vs.) (log(n))ᵇ
私はこれらの比較に何度も出くわしますが、それらを解決する良い方法を思いついたことはありません. 一般的なケースを解決するための戦術のヒントは?
[編集: これらの関数の値を計算する計算の複雑さについて話しているのではありません。私は機能自体について話している。たとえば、はforとf(n) = nの上限です。]g(n) = log(n)f(n) ≤ c g(n)c = 1n₀ > 0
log(n)^a は、正の定数 a、b に対して常に O(n^b) です。
証拠をお探しですか？このような問題はすべて、次のトリックによって、log(n) が O(n) であることを確認することで解決できます。
log(n)^a = O(n^b) は、log(n) = O(n^{b/a}) と同等です。これは、1/a べき乗は増加関数であるためです。これは、m = n^{b/a} を設定することにより、log(m^{a/b}) = O(m) と同等です。log(m^{a/b}) = (a/b)*log(m) であるため、これは log(m) = O(m) と同等です。
log(n) = O(n) は、n が 2 の累乗の場合に着目して、帰納法によって証明できます。
私はこれらの比較にたくさん遭遇します（...）一般的なケースを解決するための戦術のヒント？
あなたが一般的なケースについてであるように、そしてあなたがそのような質問に多くをフォローしていること。これが私がお勧めするものです：
知ったら、BigO表記の制限定義を使用します。
f(n) = O(g(n)) iff limit (n approaches +inf) f(n)/g(n) exists and is not +inf
数式処理システム（たとえば、オープンソースのMaxima ）を使用できます。これは、Maximaのドキュメントにあります。
log n -- O(log n)
sqrt n -- O(sqrt n)
n^2 -- O(n^2)
(log n)^2 -- O((log n)^2)
n^a対(log(n))^b
同じベースまたはパワーが必要です。したがって、数学を使用してまたはに変更n^aします。一般的なケースはありませんlog(n)^(whatever it gets to get this base)(whatever it gets to get this power)^b