-1

誰かがいくつかの質問で私を助けてくれたら本当にありがたいです.

次の再帰関数定義のそれぞれについて、マスター定理を使用して漸近的な成長順序 (つまり、Big-Tetha) を決定します。マスター定理が特定のケースに当てはまらないと思われる場合は、その理由を適切に説明してください。そのような場合でも、実行時間のある程度妥当な上限 (つまり Big-O) を提供できますか? 基本ケースはすべて定数であると想定されることに注意してください。

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

(b) T (n) = 4T(n/2) +(n^1.5) − 1

(c) T (n) = T (n/3) + 100

(d) T(n) = 125T(n/5) + n^3/logn

(e) T (n) = 2T(n/7) + log n + √n

これに関してオンラインでいくつかのことを読んだだけで、この質問に答えるのに十分な理解を得ることができません. テストのために勉強しようとしていますが、何も得られません!

どうもありがとう！

4

1 に答える 1

0

(a) を除くすべての項目は、マザーの定理で実行できます。(a) の場合、toll 関数は多項式ではないため、マスター定理は適用されません。しかし、展開によってそれを解決できます。

T(n) = 2^n + T(n/2) 
     = 2^n + 2^(n/2) + T(n/4) 
     = 2^n + 2^(n/2) + 2^(n/4) + T(n/8)
     = ... 
     = O(2^n).

繰り返しを 2 進数の合計として解釈すると、結果は明らかです: 1+10+100+10000+10000000 <= 2*10000000。

于 2013-10-16T13:28:24.140 に答える