[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:
Rahmadya Trias Handayanto 