複雑さO（log（n））はO（sqrt（n））と等価ですか？

私の教授は、入力の長さを半分にする操作では、親指のルールとしてO（log（n））の複雑さがあることを教えてくれました。それはなぜO（sqrt（n））ではないのですか？それらの両方が同等ではありませんか？複雑さO（log（n））はO（sqrt（n））と等価ですか？

出典

2017-02-04 white_tree

'log（n）'と 'sqrt（n）'のグラフを 'n == 1000 '程度までプロットしてください。 –

log（1）= 0、sqrt（1）= 1 – Sung

申し訳ありませんが、私は何を考えていたのか分かりません。ありがとう –

彼らは等価ではありません。SQRT（N）はたくさん以上ログ（N）が増加します。 Cはありませんので、sqrt（N）< C.log（N）のすべての値はNの最小値より大きくなります。

これをつかむための簡単な方法は、SQRT（N）になりつつログ（N）は、Nの（バイナリ）桁数に近い値になるということです数字の半分の数字がNにある数字です。または、平等であることの状態に：

ログ（N）= 2log （SQRT（N））

ですから、（対数を取る必要があります！）をlog （N）と同じオーダーにするためには、sqrt（N）の値を使用します。

は、例えば、11桁、0b10000000000（= 2 ）と進数のために、平方根は0b100000であるが、対数をなし、それは等価ではない唯一の10

出典

2017-02-04 08:52:51 trincot

'log（N）はNの（バイナリ）桁数に近い値になりますが、sqrt（N）はNの桁数の半分の数字になります。 –

あります。

@trincotは、彼の答えに例を挙げて1つの優れた説明を与えました。もう1つポイントを追加しています。あなたの教授は

any operation that halves the length of the input has an O(log(n)) complexity

それは

any operation that reduces the length of the input by 2/3rd, has a O(log3(n)) complexity 
any operation that reduces the length of the input by 3/4th, has a O(log4(n)) complexity 
any operation that reduces the length of the input by 4/5th, has a O(log5(n)) complexity 
So on ...

それは、その後O(logB(n))

N:B:O(logB(n))の複雑さを持っている(B-1)/Bth.ことにより、入力の長さのすべての削減のためにも本当だ、ということも事実だことを教えて平均値はBであり、対数はn

出典

2017-02-04 09:15:15 jbsu32

（そうでない場合は、単に定数を掛ける）natural logarithmと仮定すると、我々は

lim {n->inf} log n/sqrt(n) = (inf/inf)

     = lim {n->inf} 1/n/1/(2*sqrt(n)) (by L'Hospital) 
         = lim {n->inf} 2*sqrt(n)/n 
         = lim {n->inf} 2/sqrt(n) 
         = 0 < inf

を持っていることはO(.)の代替definationためhttps://en.wikipedia.org/wiki/Big_O_notationを参照し、それによって、上から我々はlog n = O(sqrt(n))、

はまた比較すると言うことができます以下の関数を使用して、log nは、nの場合、常に上限がsqrt(n)になります。

出典

2017-02-04 09:25:28

いや、彼らはない等価です。あなたも、任意のk > 0とbase > 1（sqrtの場合k = 1/2）のためにその

O(n**k) > O(log(n, base))

を証明することができます。 O(f(n))で話しているとき

たちは大n、 制限のために行動を調査したいそのための良い手段です。両方の大きなOが等価であることを仮定します

O(n**k) = O(log(n, base))

あります意味一部

O(n**k) <= C * O(log(n, base))

が十分nいくつかの大規模から始まる定数Cように有限。他の用語でそれを置く（log(n, base)が大nから始まる0ないが、両方の機能は、連続的に微分されている）：

lim(n**k/log(n, base)) = C 
    n->+inf

我々はすなわち、L'Hospital's Ruleを使用する分子と分母のためにデリバティブを取り、それらを分割することができ上限の値を調べるには：

lim(n**k/log(n)) = 

    lim([k*n**(k-1)]/[ln(base)/n]) = 

    ln(base) * k * lim(n**k) = +infinity

ので、私たちは何の定数CようO(n**k) < C*log(n, base)または他の言葉で

はありませんと結論付けることができます

出典

2017-02-04 11:57:23

複雑さO（log（n））はO（sqrt（n））と等価ですか？

答えて

関連する問題