Master Theorem

[algoritma&pemrograman/pert4/TIF-1101/r-408]

Ketika menangani kalkulasi menghitung waktu proses sorting dengan rekursif, salah satu metode yang praktis digunakan adalah master theorem. Oiya, rekursif adalah sebuah prosedur/fungsi yang didalamnya memanggil fungsi itu lagi. Misalnya pada algoritma heapshort.

  • Untuk seluruh angka
  • Ambil nilai max di akar
  • Isi akar dengan nilai index terakhir
  • Lakukan fungsi heapify()
  • Turunkan jumlah index sebanyak satu angka

Tampak ada pemanggilan fungsi heapify() di setiap rutin. Contoh lain adalah merge sort dengan devide and conquer. Dimana fungsi merge-sort() dipanggil lagi:

Master Theorem digunakan untuk mencari theta oh ataupun big oh suatu waktu proses T(n). Berikut ini rumus yang digunakan.

Langkah-langkah yang dilakukan untuk menggunakan teori ini antara lain:

  • Tentukan a, b, k dan p.
  • Cari tiga kemungkinan (lebih besar, sama dengan, atau lebih kecil) antara a dengan b^k.
  • Untuk a=b^k cek lagi apakah p>-1, p=-1, atau p<-1
  • Untuk a<b^k cek lagi apakah p>=0, atau p<0.
  • Masing-masing kemungkinan memiliki time complexity T(n) yang berbeda.

Tentu saja teori ini ada batasannya, misalnya jika di sebelah kiri T(n/b) ada n maka a tidak bisa ditentukan. Namun beberapa metode bisa mengkonversi menjadi bentuk standarnya dimana di sisi kiri berupa konstanta.

Ref:

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout /  Ubah )

Foto Google+

You are commenting using your Google+ account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )

Connecting to %s