Dalam tutorial ini, anda akan belajar apa teorema induk dan bagaimana ia digunakan untuk menyelesaikan hubungan berulang.
Kaedah induk adalah formula untuk menyelesaikan hubungan berulang bentuk:
T (n) = aT (n / b) + f (n), di mana, n = ukuran input a = bilangan sub-masalah dalam pengulangan n / b = ukuran setiap sub-masalah. Semua masalah diandaikan mempunyai ukuran yang sama. f (n) = kos kerja yang dilakukan di luar panggilan rekursif, yang merangkumi kos membahagi masalah dan kos penggabungan penyelesaian Di sini, ≧ 1 dan b> 1 adalah pemalar, dan f (n) adalah positif secara asimtotik fungsi.
Fungsi positif tanpa gejala bermaksud bahawa untuk nilai n yang cukup besar, kita mempunyai f(n)> 0.
Teorema induk digunakan dalam mengira kerumitan masa hubungan berulang (algoritma membahagi dan menaklukkan) dengan cara yang mudah dan cepat.
Teorem Sarjana
Sekiranya a ≧ 1dan b> 1adalah pemalar dan f(n)merupakan fungsi positif tanpa gejala, maka kerumitan masa hubungan rekursif diberikan oleh
T (n) = aT (n / b) + f (n) di mana, T (n) mempunyai batasan asimtotik berikut: 1. Jika f (n) = O (n log b a-ϵ ), maka T (n ) = Θ (n log b a ). 2. Sekiranya f (n) = Θ (n log b a ), maka T (n) = Θ (n log b a * log n). 3. Sekiranya f (n) = Ω (n log b a + ϵ ), maka T (n) = Θ (f (n)). is> 0 ialah pemalar.
Setiap syarat di atas dapat ditafsirkan sebagai:
- Sekiranya kos menyelesaikan sub-masalah pada setiap tahap meningkat dengan faktor tertentu, nilai
f(n)akan menjadi lebih rendah secara polinomik daripada . Oleh itu, kerumitan masa ditindas oleh kos tahap terakhir iaitu.nlogb anlogb a - Sekiranya kos menyelesaikan sub-masalah pada setiap tahap hampir sama, maka nilai
f(n)akan menjadi . Oleh itu, kerumitan masa akan menjadi kali ganda jumlah tahap iaitu.nlogb af(n)nlogb a * log n - Sekiranya kos menyelesaikan sub-masalah pada setiap tahap menurun dengan faktor tertentu, nilai
f(n)akan menjadi lebih besar daripada . Oleh itu, kerumitan masa ditindas oleh kos .nlogb af(n)
Contoh Teorem Sarjana yang Diselesaikan
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 iaitu. f (n) <n log b a + ϵ , di mana, ϵ ialah pemalar. Kes 3 tersirat di sini. Oleh itu, T (n) = f (n) = Θ (n 2 )
Batasan Teorem Master
Teorema induk tidak boleh digunakan sekiranya:
- T (n) bukan monoton. cth.
T(n) = sin n f(n)bukan polinomial. cth.f(n) = 2n- a bukan pemalar. cth.
a = 2n a < 1
