Advertisements

Contoh solusi penggunaan Master Theorem atau Metode Master untuk rekurensi

23 May

Teorema 1 (Metode Master) Diberikan suatu rekurensi T (n) = aT (n/b) + f (n) , jika n ≥ n0, untuk suatu n0 elemen N dan T (n) konstan untuk 0 ≤  n < n0. Apabila a ≥ 1, b > 1 keduanya adalah nilai yang konstan dan f (n) adalah fungsi yang asimtotik positif, maka:

master theorem

Gunakan Teorema 1 untuk mencari solusi dari setiap rekurensi berikut dalam notasi . Jika metode master tidak dapat diterapkan, gunakan metode lain yang Anda ketahui. Asumsikan bahwa T (n) konstan untuk n yang cukup kecil.

(a).  T (n) = 3T (n/2) + n.

Solusi T (n) = 3T (n/2) + n menggunakan master theorem kasus 1.

solusi master theorem 1

(b). T (n) = 2T (n/2) + n^3.

Solusi T (n) = 2T (n/2) + n^3 menggunakan master theorem kasus 3.

solusi master theorem 2

(c). T (n) = 7T (n/3) + n^2.

Solusi T (n) =  7T (n/3) + n^2 menggunakan master theorem kasus 3.solusi master theorem 3

(d).  T (n) = 2T (n/2) + n lg n.

Solusi T (n) =  2T (n/2) + n lg n menggunakan master theorem kasus 2.

solusi master theorem 4

(e). T (n) = 4T (n/2) + n^2 √n.

Solusi T (n) = 4T (n/2) + n^2 √n menggunakan master theorem kasus 3.

solusi master theorem 5

(f). T (n) = T (√n) + 1 (petunjuk: substitusikan n = 2^m).

Solusi T (n) = T (√n) + 1 menggunakan master theorem kasus 2.

solusi master theorem 6

 

(g). T (n) = 2T (n – 1) + 1 (asumsikan T (1) = 1).

Kita tidak dapat menggunakan master theorem untuk kasus ini. Dengan evaluasi iteratif, kita memiliki

solusi master theorem 7

 

(h). T (n) = T (n – 1) + lg n (asumsikan T (1) = 1).

Dengan evaluasi iteratif, kita memiliki

solusi master theorem 8-1

Dengan sifat logaritma lg a + lg b = lg ab, diperoleh

solusi master theorem 8-2

Dengan aproksimasi Stirling,  lg (n!) = Θ(n lg n). Akibatnya T (n) = 1 +Θ (n lg n) = Θ(n lg n)

(i). T (n) = T (n – 2) + 2 lg n (asumsikan T (0) = 2).

Karena paritas (genap-ganjil) dari n tidak berpengaruh pada nilai T (n) secara asimtotik, kita boleh mengasumsikan n genap. Dengan evaluasi iteratif, kita memiliki

solusi master theorem 9-1 solusi master theorem 9-2

(j). T (n) = √n T (√n) + 2013 n (petunjuk: misalkan T (n) = nS (n) dengan S (n) adalah fungsi yang asimtotik positif).

Misalkan T (n) = nS (n), maka T (√n) = √n S (√n). Akibatnya rekurensi pada soal setara dengan

solusi master theorem 10-1 solusi master theorem 10-2Demikianlah contoh penggunaan master theorem dalam masalah rekurensi, semoga bermanfaat!

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: