Equazioni ricorrenza

[manowar]

$ 3T(n/3) + n log n $

Qui non è possibile usare il teorema master quindi ho pensato di srotolare la ricorsione
ottendo $3^i(n/3^i)$ $ i=log in base 3 di n $
poi non so come continuare ,non è una serie geometica ,
secondo me dovrebbe essere qualcosa come $ O(n log log n)

[hamming_burst]

Ciao,
benvenuto

vediamo, quello che tu chiami "srotolare" si chiama "metodo dell'iterazione"; solo per dare un termine meno culinario

Questo tipo di ricorrenze io di solito le mostro con il metodo dell'albero di ricorsione, un metodo equivalente al metodo algebrico/dell'iterazione;

$T(n) = 3T(n/3) + nlogn$

$nlogn = 3^0*(n/3^0*log(n/3^0))$

$n/3*log(n/3)\ \ \ \ \ \ n/3*log(n/3) \ \ \ \ \ \ n/3*log(n/3) = 3*(n/3*log(n/3)) = (3^1)*(n/3*log(n/3))$

$n/9*log(n/9)\ \ \ \ \ \ n/9*log(n/9) \ \ \ \ \ \ n/9*log(n/9)\ \ \ \ ...\ \ \ \ \ n/9*log(n/9)\ \ \ \ \ \ n/9*log(n/9) \ \ \ \ \ \ n/9*log(n/9) = (3+3+3)*(n/9*log(n/9)) = (3^2)*(n/9*log(n/9))$

....

$3^i((n/3^i)*log(n/3^i) = n*log(n/3^i) = n*(log(n)-i*log(3))$

l'altezza dell'albero $h=log_3(n)$ dalla proprietà degli alberi ed è il valore che annulla la divisione $n/3^i$

perciò, sommiamo tutti i nodi interni dell'albero ($h-1 = log_3(n)-1$):

$sum_{i=0}^{log_3(n)-1} n*(log_3(n)-i*log_3(3)) = sum_{i=0}^{log_3(n)-1} n*(log_3(n)-i) = n*sum_{i=0}^{log_3(n)-1} log_3(n)-i$

$n*sum_{i=0}^{log_3(n)-1} log_3(n)-i = n*sum_{k=1}^{log_3(n)} k = n*((log_3(n)*(log_3(n)+1))/2) = 1/2n*log_{3}^{2}(n) + 1/2n*log_{3}(n) = n*log_{3}^{2}(sqrt(n)) + n*log_{3}(sqrt(n))$

ora bisogna calcolare il numero di foglie dell'albero ($h=log_3(n)$)

$n*log(n/3^(log_3(n))) = 0 in O(1)$

perciò, sommiamo tutto quello trovato (nodi interni + foglie): $n*log_{3}^{2}(sqrt(n)) + n*log_{3}(sqrt(n)) + O(1) in O(n*log_{3}^{2}(sqrt(n)))$

La complessità dell'equazione di ricorrenza: $T(n) = 3T(n/3) + nlogn in O(n*log_{3}^{2}(sqrt(n)))$

per fare le cose bene sarebbe da utilizzare l'induzione matematica e dimostrare che questa limitazione è vera, ma così comunque ti da una limitazione (ipotizzata) esatta.
Forse non capirari tutti i passaggi, ma ti ho mostrato tutto così comprendi i calcoli che con il tuo metodo non riesci a vedere bene.

Se hai dubbi chiedi pure