κλειστός τύπος αναδρομής

jim · #1

$T(n)=2T(\frac{n}{4})+log_{4}n$ με T(1)=0

και θεωρείστε ότι το n είναι δύναμη του 4.. Να βρεθεί ο κλειστός τύπος

Με επαναληπτική μέθοδο μάλλον βγαίνει αλλά κολλάω, νομίζω πως βγαίνει τόσο: $T(n)=2^{k}T(\frac{n}{4^{k}})+log_{4}n+2log_{4}\frac{n}{4}+...+2^{k-1}log_{4}(\frac{n}{4^{k-1}})$ Πόσο βγαίνει το T(n);

jim · #2

Στην ουσία δεν είμαι σίγουρος για το άθροισμα που προκύπτει από τα log. Είναι: $\sum_{0}^{k-1}{2^{i}log_{4}(\frac{n}{4^{i}})}$

jim · #3

Τελικά ο κλειστός τύπος είναι ο: $(log_{4}n-\frac{k(k-1)}{2})(2^{k}-1)$ ;

κλειστός τύπος αναδρομής

κλειστός τύπος αναδρομής

Re: κλειστός τύπος αναδρομής

Re: κλειστός τύπος αναδρομής

Μέλη σε σύνδεση