mathematica.gr

Δημοσιεύτηκε: **Δευ Ιαν 23, 2012 8:35 pm**

$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);

Δημοσιεύτηκε: **Δευ Ιαν 23, 2012 8:44 pm**

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

Δημοσιεύτηκε: **Δευ Ιαν 23, 2012 9:03 pm**

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

mathematica.gr

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

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

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

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