Teorema Master (Dengan Contoh)

Dalam tutorial ini, Anda akan mempelajari apa itu teorema master dan bagaimana teorema itu digunakan untuk menyelesaikan hubungan pengulangan.

Metode master adalah rumus untuk menyelesaikan hubungan pengulangan bentuk:

T (n) = aT (n / b) + f (n), di mana, n = ukuran input a = jumlah submasalah dalam rekursi n / b = ukuran setiap subproblem. Semua subproblem diasumsikan memiliki ukuran yang sama. f (n) = biaya pekerjaan yang dilakukan di luar panggilan rekursif, yang meliputi biaya membagi masalah dan biaya penggabungan solusi Di sini, a ≧ 1 dan b> 1 adalah konstanta, dan f (n) adalah positif asimtotik fungsi.

Fungsi positif asimtotik berarti bahwa untuk nilai n yang cukup besar, kita punya f(n)> 0.

Teorema master digunakan untuk menghitung kompleksitas waktu dari relasi pengulangan (algoritma membagi dan menaklukkan) dengan cara yang sederhana dan cepat.

Teorema Utama

Jika a ≧ 1dan b> 1adalah konstanta dan f(n)merupakan fungsi positif asimtotik, kompleksitas waktu dari relasi rekursif diberikan oleh

T (n) = aT (n / b) + f (n) di mana, T (n) memiliki batas asimtotik berikut: 1. Jika f (n) = O (n log b a-ϵ ), maka T (n ) = Θ (n log b a ). 2. Jika f (n) = Θ (n log b a ), maka T (n) = Θ (n log b a * log n). 3. Jika f (n) = Ω (n log b a + ϵ ), maka T (n) = Θ (f (n)). ϵ> 0 adalah konstanta.

Masing-masing kondisi di atas dapat diartikan sebagai:

  1. Jika biaya penyelesaian sub-masalah di setiap level meningkat dengan faktor tertentu, nilai dari f(n)akan menjadi lebih kecil dari . Dengan demikian, kompleksitas waktu ditekan oleh biaya tingkat terakhir yaitu.nlogb anlogb a
  2. Jika biaya untuk menyelesaikan sub-masalah di setiap level hampir sama, maka nilai dari f(n)akan menjadi . Dengan demikian, kompleksitas waktu akan dikalikan dengan jumlah total level yaitu.nlogb af(n)nlogb a * log n
  3. Jika biaya penyelesaian sub-masalah di setiap tingkat berkurang dengan faktor tertentu, nilai dari f(n)akan menjadi lebih besar dari . Dengan demikian, kompleksitas waktu tertekan oleh biaya .nlogb af(n)

Contoh Soal Teorema Utama

T (n) = 3T (n / 2) + n2 Di sini, a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1,58 <2 yaitu. f (n) <n log b a + ϵ , di mana, ϵ adalah konstanta. Kasus 3 tersirat di sini. Jadi, T (n) = f (n) = Θ (n 2 )

Keterbatasan Teorema Induk

Teorema master tidak dapat digunakan jika:

  • T (n) tidak monoton. misalnya.T(n) = sin n
  • f(n)bukan polinomial. misalnya.f(n) = 2n
  • a bukanlah sebuah konstanta. misalnya.a = 2n
  • a < 1

Artikel yang menarik...