Complessita' ricorrenza lineare
Ciao a tutti, sto cercando di fare un esercizio ma non sono molto sicuro di cio' che ho fatto. Espongo a voi i miei dubbo, magari potete aiutarmi.
Data $T(n) = 2T(n/2)+nlogn$ calcolarne il limite superiore.
Prima di tutto ho provato col teorema dell'esperto. Il caso che piu' si avvicinava è il terzo ($T(n) = \Omega(n^(log_ba+\epsilon))$) ma non va bene. Quindi devo trovare altre vie. Ho poi pensato alle ricorrenze lineari con partizione bilanciata dato che c'e' un teorema che potrebbe aiutarmi pero'... questo teorema richiede che la ricorrenza sia della forma:
$T(n) = aT(n/b)+cn^\beta$ ma io ho $T(n) = aT(n/b)+f(n)$ con $f(n)= nlogn$ quindi nulla.
Al che ho detto: provo col metodo della sostituzione:
a ogni iterazione ho un $nlogn$ e l'iterazione viene fatta fin tanto che $n/2 > 1$ quindi sara' fatta $logn$ volte.
Quindi mi aspetterei un costo massimo del tipo $2*(logn) *nlogn$.
Quindi procedo col tentativo di dimostrazione:
$T(n)= 2T(n/2)+ nlogn <= cn*logn*logn$
$<= 2c(n/2)*log(n/2)*log(n/2)+ nlogn$
$= cn*(logn-log2)*(logn-log2)+ nlogn$
$= cn*(logn-1)*(logn-1)+ nlogn<=cn*logn*logn$
Pero' c'è quel $+ nlogn$ che mi frega... devo tentare così: $T(n)= 2T(n/2)+ nlogn <= c(n-nlogn)*logn*logn$ ??
Data $T(n) = 2T(n/2)+nlogn$ calcolarne il limite superiore.
Prima di tutto ho provato col teorema dell'esperto. Il caso che piu' si avvicinava è il terzo ($T(n) = \Omega(n^(log_ba+\epsilon))$) ma non va bene. Quindi devo trovare altre vie. Ho poi pensato alle ricorrenze lineari con partizione bilanciata dato che c'e' un teorema che potrebbe aiutarmi pero'... questo teorema richiede che la ricorrenza sia della forma:
$T(n) = aT(n/b)+cn^\beta$ ma io ho $T(n) = aT(n/b)+f(n)$ con $f(n)= nlogn$ quindi nulla.
Al che ho detto: provo col metodo della sostituzione:
a ogni iterazione ho un $nlogn$ e l'iterazione viene fatta fin tanto che $n/2 > 1$ quindi sara' fatta $logn$ volte.
Quindi mi aspetterei un costo massimo del tipo $2*(logn) *nlogn$.
Quindi procedo col tentativo di dimostrazione:
$T(n)= 2T(n/2)+ nlogn <= cn*logn*logn$
$<= 2c(n/2)*log(n/2)*log(n/2)+ nlogn$
$= cn*(logn-log2)*(logn-log2)+ nlogn$
$= cn*(logn-1)*(logn-1)+ nlogn<=cn*logn*logn$
Pero' c'è quel $+ nlogn$ che mi frega... devo tentare così: $T(n)= 2T(n/2)+ nlogn <= c(n-nlogn)*logn*logn$ ??
Risposte
A me sembra che si possa fare con il master theorem.. Ti consiglio di ricontrollare le condizione dei tre casi.
[strike]Ad ogni iterazione non hai \(n\,\log n\). Devi infatti sostituire \(n\) con \(n/2^k\). Hai quindi ..[/strike]
In effetti, usando il master theorem si arriva a concludere che \( T(n) \in \Theta(n\,(\log n)^2). \) La tua ipotesi non era quindi granché diversa dalla realtà.
Venendo al discorso della presenza di \(n\,\log n\).. Per prima cosa puoi osservare che
\[ c\,n\,(\log n - 1)^2 = c\,n\,(\log n)^2 - 2\,c\,n\,\log n + c\,n. \]
Se a questo punto sommi \( n\,\log n \) a questo valore ottieni
\[ c\,n\,(\log n)^2 + (1 - 2\,c)\,n\,\log n + c\,n \]
A questo punto devi solo chiederti se per un valore sufficientemente grande \( (1 - 2\,c)\,\log n + c \) è negativo. Ma questo è certamente vero se si prende un valore di \(c > 0\).
EDIT: Cancellato parte sbagliata.
[strike]Ad ogni iterazione non hai \(n\,\log n\). Devi infatti sostituire \(n\) con \(n/2^k\). Hai quindi ..[/strike]
In effetti, usando il master theorem si arriva a concludere che \( T(n) \in \Theta(n\,(\log n)^2). \) La tua ipotesi non era quindi granché diversa dalla realtà.
Venendo al discorso della presenza di \(n\,\log n\).. Per prima cosa puoi osservare che
\[ c\,n\,(\log n - 1)^2 = c\,n\,(\log n)^2 - 2\,c\,n\,\log n + c\,n. \]
Se a questo punto sommi \( n\,\log n \) a questo valore ottieni
\[ c\,n\,(\log n)^2 + (1 - 2\,c)\,n\,\log n + c\,n \]
A questo punto devi solo chiederti se per un valore sufficientemente grande \( (1 - 2\,c)\,\log n + c \) è negativo. Ma questo è certamente vero se si prende un valore di \(c > 0\).
EDIT: Cancellato parte sbagliata.
GRazie mille della risposta.
Hai ragione. Ho rifatto i calcoli. Scusami la svista.
Non ho capito perchè ad ogni iterazione non ho \(n\,\log n\), perchè $2^(-k)$?
"apatriarca":
A me sembra che si possa fare con il master theorem.. Ti consiglio di ricontrollare le condizione dei tre casi.
Hai ragione. Ho rifatto i calcoli. Scusami la svista.
"apatriarca":
Ad ogni iterazione non hai \(n\,\log n\). Devi infatti sostituire \(n\) con \(n/2^k\). Hai quindi
\[ 2^{-k}\,n\,\log 2^{-k}\,n = 2^{-k}\,(\log n - k\,n). \]
Non ho capito perchè ad ogni iterazione non ho \(n\,\log n\), perchè $2^(-k)$?
In effetti hai ragione tu.. Mi sono dimenticato di fare la somma di tutti i contributi ad un particolare livello. Anche il metodo dell'albero che hai usato è comunque valido come dimostrazione.
Grazie a te!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo