Memecahkan Persamaan Perulangan yang mengandung dua Panggilan Rekursi

15

Saya mencoba untuk menemukan terikat untuk persamaan perulangan berikut: $\Theta$

T (n) = 2 T (n / 2) + T (n / 3) + 2 n^{2} + 5 n + 42

$T(n) = 2 T(n/2) + T(n/3) + 2n^2+ 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(1)$ $T(0)$

asymptotics recurrence-relation master-theorem 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.

T (n) \leq 42

$T(n) \leq 42$

n < 100

$n < 100$

T (n) = 2^{m}

$T(n) = 2^m$

n < 100

$n < 100$

m

$m$

Alex ten Brink

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(10^{100})$ . 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)+n^2$

Akar pohon rekursi memiliki nilai . $n^2$
Root memiliki tiga anak, dengan nilai , , dan . Dengan demikian, nilai total dari semua anak-anak adalah . $(n/2)^2$ $(n/2)^2$ $(n/3)^2$ $(11/18) n^2$
Sanity check: Root memiliki sembilan cucu: empat dengan nilai , empat dengan nilai , dan satu dengan nilai . Jumlah dari nilai-nilai adalah . $(n/4)^2$ $(n/6)^2$ $(n/9)^2$ $(11/18)^2 n^2$
Bukti induksi mudah menyiratkan bahwa untuk setiap bilangan bulat , yang node di tingkat memiliki nilai total . $\ell\ge 0$ $3^\ell$ $\ell$ $(11/18)^\ell n^2$
Jumlah yang tingkat membentuk turun seri geometris, sehingga hanya istilah terbesar hal. $\ell=0$
Kami menyimpulkan bahwa . $T(n) = \Theta(n^2)$

JeffE
sumber

14

Anda dapat menggunakan metode Akra-Bazzi yang lebih umum .

Dalam kasus Anda, kami perlu mencari seperti itu $p$

\frac{1}{2^{p - 1}} + \frac{1}{3^{p}} = 1

$\frac{1}{2^{p-1}} + \frac{1}{3^p} = 1$

(yang menghasilkan ) $p \approx 1.364$

dan kemudian kita miliki

T (x) = Θ (x^{p} + x^{p} \int_{1}^{x} t^{1 - p} d t) = Θ (x^{2})

$T(x) = \Theta(x^p + x^p\int_{1}^{x} t^{1-p} \text{d}t) = \Theta(x^2)$

Perhatikan bahwa Anda tidak benar-benar perlu menyelesaikannya untuk . Yang perlu Anda ketahui adalah bahwa . $p$ $1 \lt p \lt 2$

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

Aryabhata
sumber

14

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

3 T (n / 3) + 2 n^{2} + 5 n + 42 \leq f (n) \leq 3 T (n / 2) + 2 n^{2} + 5 n + 42

$3 T(n/3) + 2n^2+ 5n + 42 \quad \le\quad f(n) \quad\leq \quad 3 T(n/2) + 2n^2+ 5n + 42 \quad$

If we use the lower resp. upper bound as right-hand side of the recurrence, we get $T'(n) \in \Theta(n^2)$ in both cases by the Master theorem. Thus, $T(n)$ is bounded from above by $O(n^2)$ and from below by $\Omega(n^2)$ or, equivalently, $T(n) \in \Theta(n^2)$ .

For a complete proof, you should prove that $T$ is an increasing function.

Raphael
sumber

let us continue this discussion in chat

Raphael

1

That trick won't work for similar recurrences, like

T (n) = 2 T (n / 2) + 3 T (n / 3) + n^{2}

$T(n) = 2T(n/2) + 3T(n/3) + n^2$ , that can be solved with recursion trees. (But even recursion trees won't work for

T (n) = 2 T (n / 2) + 4 T (n / 3) + n^{2}

$T(n) = 2T(n/2) + 4T(n/3) + n^2$ , which can be solved with Akra-Bazzi.)

JeffE

Memecahkan Persamaan Perulangan yang mengandung dua Panggilan Rekursi

Jawaban: