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:

Tentang rahmadya

I'm a simple man .. Lahir di Sleman Yogyakarta, 7 Juni 1976 PENDIDIKAN: TK : - (tidak ada TK di tj Priok waktu itu) SDN : Papanggo, Jakarta 83 - 89 SMPN : 129, Jakarta 89 - 92 SMAN : 8, Yogyakarta 92 - 95 Univ. : Fak. Teknik UGM, Yogyakarta 95 - 2001 Pasca. : Tek. Informatika STMIK Nusa Mandiri, Jakarta 2008 - 2010 Doctoral : Information Management Asian Institute of Technology, Thailand 2013 - 2018 PEKERJAAN: Tek. Komputer AMIK BSI Jakarta : 2002 - 2005 IT Danamon Jakarta : 2005 - 2008 Tek. Informatika STMIK Nusa Mandiri Jakarta : 2005 - 2008 Univ. Darma Persada Jakarta: 2008 - 2013 Fakultas Teknik Universitas Islam "45" Bekasi : 2008 - Skrg ( Homebase) Univ. Bhayangkara Jakarta Raya: 2018 - Skrg Univ. Nusa Putra Sukabumi: 2018 - Skrg
Pos ini dipublikasikan di Algoritma. Tandai permalink.

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.