Equazione di ricorrenza

Messaggioda sara09 » 11/01/2020, 11:51

Buongiorno se ho questa equazione di ricorrenza:
$ {( 1 ) , ( 4T(sqrt(n))+log_2(n) ):} $
Nei nodi del secondo livello nell’albero di derivazione ho:
1) $ sqrt(log_2(n)) $
Oppure
2) $ log_2(sqrt(n)) $
Grazie in anticipo ☺️
sara09
Junior Member
Junior Member
 
Messaggio: 152 di 166
Iscritto il: 11/02/2019, 19:04

Re: Equazione di ricorrenza

Messaggioda probid » 11/01/2020, 15:47

Come hai ottenuto quei costi?
Se non sbaglio, al livello $i$-esimo dovrebbe essere \( 4^i log \sqrt[2^i]{n} = 2^i log n \)...
probid
Starting Member
Starting Member
 
Messaggio: 38 di 38
Iscritto il: 01/10/2010, 19:30

Re: Equazione di ricorrenza

Messaggioda apatriarca » 13/01/2020, 13:36

@probid Penso stiate dicendo la stessa cosa. Nel secondo livello dell'albero ci saranno 4 nodi di costo \(\log\,\sqrt{n} = (\log\,n) / 2\). Penso che il dubbio fosse se applicare la radice sostituendo \(n\) con \(\sqrt{n}\) (il metodo corretto) oppure applicarlo a tutta la funzione.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5340 di 5371
Iscritto il: 08/12/2008, 20:37
Località: Londra

Re: Equazione di ricorrenza

Messaggioda sara09 » 19/01/2020, 10:17

apatriarca ha scritto:@probid Penso stiate dicendo la stessa cosa. Nel secondo livello dell'albero ci saranno 4 nodi di costo \(\log\,\sqrt{n} = (\log\,n) / 2\). Penso che il dubbio fosse se applicare la radice sostituendo \(n\) con \(\sqrt{n}\) (il metodo corretto) oppure applicarlo a tutta la funzione.

Si infatti questo intendevo..
Grazie mille
sara09
Junior Member
Junior Member
 
Messaggio: 153 di 166
Iscritto il: 11/02/2019, 19:04


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 4 ospiti