Semplificazione di una ricorrenza
Ciao a tutti,
non sono molto sicuro che sia questa la sezione migliore per il mio posto. E' un problema di Algoritmi e strutture dati ma il problema che ho è di tipo algebrico.
Ho una domanda su una ricorrenza della quale devo trovare la complessita': $T(n) = 2T(n^(1/2))+log n$
Quotero' i passaggi suggeriti dal libro e sotto il quote faro' le mie domande.
Ok, chiaro!
Ecco, qua non ho mica capito. Come ha sostituito e come ha semplificato?
Mi spiego meglio: Ho capito che ha preso la funzione $T$ che ha come parametro $2^m$ e ha detto: mi costruisco una funzione $S$ che prenda "solo l'esponente del paramento di $T$" (perdonate la spiegazione brutale che faccio) e quindi il mio $2^(m/2)$ diventa $m/2$.
Pero' non mi è per nulla chiaro come abbia fatto qul $log 2^m$ a diventare $m$.
Ehm, ora che rileggo cio' che ho scritto mi viene in mente una spiegazione banale ed ovvia: $log 2^m = m*log 2 = m*1$. giusto?
Vi spiego quello che avevo pensato prima io: se applico $S(m)$ a $log 2^m$ ottengo $log m$ che evidentemente era sbagliato. Potete dirmi perchè dato che io posso scrivere $log 2^m = log(2^m)$ il che è come dire $f(g(m))$ e dato che io applico la mia $S$ a $2^m$, l'avrei applicato a $log (2^m)$ ed avrei avuto $log m$. Dove ho toppato?
Grazie a tutti
non sono molto sicuro che sia questa la sezione migliore per il mio posto. E' un problema di Algoritmi e strutture dati ma il problema che ho è di tipo algebrico.
Ho una domanda su una ricorrenza della quale devo trovare la complessita': $T(n) = 2T(n^(1/2))+log n$
Quotero' i passaggi suggeriti dal libro e sotto il quote faro' le mie domande.
sostituire $n = 2^m$ ed otteniamo $T(2^m) = 2T(2^(m/2))+log 2^m$
Ok, chiaro!
Poniamo $S(m) = T(2^m)$ e otteniamo $S(m) = 2S(m/2)+m$.
Ecco, qua non ho mica capito. Come ha sostituito e come ha semplificato?
Mi spiego meglio: Ho capito che ha preso la funzione $T$ che ha come parametro $2^m$ e ha detto: mi costruisco una funzione $S$ che prenda "solo l'esponente del paramento di $T$" (perdonate la spiegazione brutale che faccio) e quindi il mio $2^(m/2)$ diventa $m/2$.
Pero' non mi è per nulla chiaro come abbia fatto qul $log 2^m$ a diventare $m$.
Ehm, ora che rileggo cio' che ho scritto mi viene in mente una spiegazione banale ed ovvia: $log 2^m = m*log 2 = m*1$. giusto?
Vi spiego quello che avevo pensato prima io: se applico $S(m)$ a $log 2^m$ ottengo $log m$ che evidentemente era sbagliato. Potete dirmi perchè dato che io posso scrivere $log 2^m = log(2^m)$ il che è come dire $f(g(m))$ e dato che io applico la mia $S$ a $2^m$, l'avrei applicato a $log (2^m)$ ed avrei avuto $log m$. Dove ho toppato?
Grazie a tutti
Risposte
Il logaritmo si intende sicuramente in base \(2\).
è legittimo scrivere: $T(2^(n/2)) = T(2^(n * (1/2))) = T((2^n)^(1/2)) = S(m^(1/2))$ ? nell'ultimo passaggio, ho sostituito: $n = 2^m, S(m) = T(2^m)$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo