問題タブ [master-theorem]

誰かがこの解決策をもう少し明確にしてもらえますか?

T(n) = 2T(n^1/2) + ログ n

解決：

k = log n とします。

T(n) = T(2^k)=2T(2^(k/2)) + k

これに式 S(k) = T(2^k) を代入します。

私たちはそれを得る

S(k)=2S(k/2) + k

さて、この再帰方程式により、マスター定理を使用することができます。

S(k) は O(k log k) です。T(n) の代入は、T(n) が O(log n log log n) であることを意味します。

実行時間を計算したいアルゴリズムは次のとおりです。

n は正の自然数の一部で、c0 と c1 は定数です。

Javaコードのアルゴリズムは次のとおりです。

アプローチまたは説明の例を探しています。

私は友人と口論しています.昨日試験がありました.私はそれができないと言った.彼はそれがケース1になると言った.おそらく彼は正しい. 前もって感謝します。

マスター定理の証明を理解するために Thomas H. Cormen の本を読んでいました。

ありがとう

f(n) が何であるかわかりませんか? n^2 ですか 2n^2 + n/3 ですか? そのような質問をどのように解決しますか？前もって感謝します

この再帰を解決しようとしています:

ただし、f(n) は定数 -sqrt(n)

私の質問:

1. f(n) = Theta(sqrt n) と仮定できますか、それとも知っておくべきトリックはありますか?

2. また、あなたがそれをしている間に、定数マイナスsqrt（n）を持っているかどうかを説明できれば、つまりマイナス記号は何か意味がありますか? または無視できます。

これは私を夢中にさせています！助けてください！ありがとう！！