1

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

T(n) = 4T(n/2) + 2500 - sqrt(n)
here a = 4, b=2 but my f(n) = 2500 -sqrt(n) 
n^ logb(a) = n ^ log2 (4) = n ^2

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

私の質問:

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

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

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

4

1 に答える 1

5

マスター定理には、いくつかの前提条件とケース要件があります。それらのいずれかに違反すると、定理またはケースは適用されません。私が見る限り、このケースは f(n) が正であるという定理の要件に違反しています。

実際には、これは、2500^2 ノードを通過すると、プロセス間通信のオーバーヘッドが負になることを意味します。結果は、計算が完了する前に収集および照合されます。

問題文に間違いがあるのではないかと強く疑っています。

于 2016-09-26T17:33:53.810 に答える