私はこの方程式を解くのに苦労しています。この状況ではマスター定理は当てはまらないと結論付けたので、この方程式を解くために項を続けて置き換えようとしましたが、先に進むことができません。誰かがこれを解決するための最良の方法を教えてもらえますか？
ありがとう
2056 次
1 に答える
1
あなたが推測したように、ケース3の条件が失敗したため、マスター定理を使用できません。
ただし、最初はn ^（log_b a）= n（log_2 2）=nです。
今n<n* log（log（n））
したがって、再帰項2T（n / 2）の寄与は、他の項n *（log（log n））と比較して減少し続けます。したがって、今のところその項を忘れることができます...
ここで、用語n（log（log n））について考えます。
再発を拡大しますが、私たちはこの用語を重要視しています、私たちは、
T（n）= 2 ^ k * T（n / 2 ^ k）+ n [log（log（n / 2 ^（k-1）））+ log（log（n / 2 ^（k-2）） .....]
2 ^ kをnとして置くと、
T（n）=最初の項を無視+ n [log（log（2））+ log（log（4））+ ..... + log（log（2 ^（k-1）））]
T（n）=最初の項を無視+ n [log（1）+ log（2）+ log（3）+ ...... + log（k-1）]
T（n）=最初の項を無視+ n [log（（k-1）！）]
必要なのは上限だけなので、スターリングの近似を利用できます。
n！<（n / e）^ n
したがって（k-1）！〜（（k-1）/ e）^（k-1）
したがって、log（（k-1）！）=（k-1）[（log（k-1）-log（e）]
ただし、k = log n => [log（（k-1）！）] =（log（n）-1）[log（log（n）-1-log（e）]
したがって、項n [log（（k-1）！）] = n * log（n）* log（log（n））および無視できるいくつかの低次の項。
したがって、答えは次のとおりです。O（n * log（n）* log（log（n）））
PS：私はこの答えがわかりません、私がいくつかの誤りを犯したかどうかをチェックして教えてください！
于 2012-06-11T07:53:34.050 に答える