Memecahkan Persamaan Perulangan yang mengandung dua Panggilan Rekursi

15

Saya mencoba untuk menemukan terikat untuk persamaan perulangan berikut:Θ

T(n)=2T(n/2)+T(n/3)+2n2+5n+42

Saya pikir Teorema Master tidak tepat karena jumlah subproblem dan divisi yang berbeda. Pohon rekursi juga tidak berfungsi karena tidak ada atau lebih tepatnya .T ( 0 )T(1)T(0)

Laura
sumber
5
Jika Anda memiliki pengulangan formulir itu, HARUS ada kasus dasar, katakanlah untuk semua . Jika tidak, maka tidak ada yang mengatakan apa yang akan diselesaikan oleh perulangan: mungkin untuk semua , di mana adalah ukuran dari masalah aslinya! (bayangkan rekursi yang berakhir dengan membandingkan jumlah konstan dari apa pun yang Anda rekur ke semua himpunan bagian dari elemen asli) Dengan kata lain: tidak ada kasus dasar berarti tidak cukup informasi untuk menyelesaikan perulangan. n < 100 T ( n ) = 2 m n < 100 mT(n)42n<100T(n)=2mn<100m
Alex ten Brink

Jawaban:

15

Ya, pohon rekursi masih berfungsi! Tidak masalah sama sekali apakah base case terjadi pada T(0) atau T(1) atau T(2) atau bahkan T(10100) . Juga tidak masalah apa nilai aktual dari kasus dasar; apa pun nilainya, itu adalah konstan.

Dilihat melalui kacamata Theta besar, perulangannya adalah .T(n)=2T(n/2)+T(n/3)+n2

  • Akar pohon rekursi memiliki nilai .n2

  • Root memiliki tiga anak, dengan nilai , ( n / 2 ) 2 , dan ( n / 3 ) 2 . Dengan demikian, nilai total dari semua anak-anak adalah ( 11 / 18 ) n 2 .(n/2)2(n/2)2(n/3)2(11/18)n2

  • Sanity check: Root memiliki sembilan cucu: empat dengan nilai , empat dengan nilai ( n / 6 ) 2 , dan satu dengan nilai ( n / 9 ) 2 . Jumlah dari nilai-nilai adalah ( 11 / 18 ) 2 n 2 .(n/4)2(n/6)2(n/9)2(11/18)2n2

  • Bukti induksi mudah menyiratkan bahwa untuk setiap bilangan bulat , yang 3 node di tingkat memiliki nilai total ( 11 / 18 ) n 2 .03(11/18)n2

  • Jumlah yang tingkat membentuk turun seri geometris, sehingga hanya istilah terbesar hal.=0

  • Kami menyimpulkan bahwa .T(n)=Θ(n2)

JeffE
sumber
14

Anda dapat menggunakan metode Akra-Bazzi yang lebih umum .

Dalam kasus Anda, kami perlu mencari seperti itup

12p1+13p=1

(yang menghasilkan )p1.364

dan kemudian kita miliki

T(x)=Θ(xp+xp1xt1pdt)=Θ(x2)

Perhatikan bahwa Anda tidak benar-benar perlu menyelesaikannya untuk . Yang perlu Anda ketahui adalah bahwa 1 < p < 2 .p1<p<2

Metode yang lebih sederhana adalah dengan menetapkan , dan coba buktikan bahwa g ( x ) dibatasi.T(x)=x2g(x)g(x)

Aryabhata
sumber
14

Biarkan menjadi singkatan untuk sisi kanan dari perulangan. Kami menemukan batas bawah dan atas untuk f dengan menggunakan T ( n / 3 ) T ( n / 2 ) :f(n)=2T(n/2)+T(n/3)+2n2+5n+42fT(n/3)T(n/2)

3T(n/3)+2n2+5n+42f(n)3T(n/2)+2n2+5n+42

If we use the lower resp. upper bound as right-hand side of the recurrence, we get T(n)Θ(n2) in both cases by the Master theorem. Thus, T(n) is bounded from above by O(n2) and from below by Ω(n2) or, equivalently, T(n)Θ(n2).


  1. For a complete proof, you should prove that T is an increasing function.
Raphael
sumber
1
That trick won't work for similar recurrences, like T(n)=2T(n/2)+3T(n/3)+n2, that can be solved with recursion trees. (But even recursion trees won't work for T(n)=2T(n/2)+4T(n/3)+n2, which can be solved with Akra-Bazzi.)
JeffE