Passa al tema normale
Discussioni su argomenti di Informatica

Regole del forum

Consulta il nostro regolamento e la guida per scrivere le formule
Rispondi al messaggio

Equazione di ricorrenza

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 ☺️

Re: Equazione di ricorrenza

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 \)...

Re: Equazione di ricorrenza

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.

Re: Equazione di ricorrenza

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
Rispondi al messaggio


Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000— Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.