ESERCIZI VARI SU RICORRENZE (ASD)

Messaggioda Giova411 » 16/04/2014, 21:14

Volevo iniziare una "raccolta di ricorrenze".
Questo per non aprire ogni volta un Topic nuovo per ogni ricorrenza...
Iniziamo!
Mi sapreste aiutare con la seguente?

\(\ T (n) = 3T \sqrt(n) + log n \)

Ho provato a sostituire \( m = lg n \) per avere \( T(2^m) = 3 T(2^{1/2 m}) + m \)
poi ancora \( S(m) = T(2^m) \) non so se arrivo correttamente a \( S(m) = 3 S(m/2) + m \)
dopo questo, sempre se corretto, mi perdo....
Giova411
Advanced Member
Advanced Member
 
Messaggio: 1599 di 2254
Iscritto il: 16/11/2006, 00:34

Re: ESERCIZI VARI SU RICORRENZE (ASD)

Messaggioda Giova411 » 16/04/2014, 22:18

Grazie Tem, ma non credo sia giusto però
Giova411
Advanced Member
Advanced Member
 
Messaggio: 1600 di 2254
Iscritto il: 16/11/2006, 00:34

Re: ESERCIZI VARI SU RICORRENZE (ASD)

Messaggioda Giova411 » 17/04/2014, 17:37

Per quanto interessante non lo capisco bene quel sito :roll:


Partendo sempre dalle origini:
\(\ T (n) = 3T \sqrt(n) + log n \)
Secondo i miei calcoli potrebbe venire tipo:
\(\displaystyle T(n) \in \Theta( lg n^{lg 3} )\) ??
Giova411
Advanced Member
Advanced Member
 
Messaggio: 1601 di 2254
Iscritto il: 16/11/2006, 00:34

Re: ESERCIZI VARI SU RICORRENZE (ASD)

Messaggioda hamming_burst » 17/04/2014, 17:45

dai un occhio a questo.
hamming_burst
Cannot live without
Cannot live without
 
Messaggio: 4093 di 8058
Iscritto il: 04/07/2009, 10:53

Re: ESERCIZI VARI SU RICORRENZE (ASD)

Messaggioda Giova411 » 17/04/2014, 18:02

hamming_burst ha scritto:dai un occhio a questo.

LO VEDI DOV'E' HAMMMING!!!!!! =)
Dov'eri finito?!?!?
Visto l'esempio!!! (dove cantavi e suonavi da solista :-({|= )

Quindi suppongo sia giusto anche il mio esercizio :shock:
Giova411
Advanced Member
Advanced Member
 
Messaggio: 1602 di 2254
Iscritto il: 16/11/2006, 00:34

Re: ESERCIZI VARI SU RICORRENZE (ASD)

Messaggioda Giova411 » 21/04/2014, 15:03

Dopo la ricorrenza di cui sopra, che spero abbia un ordine di grandezza preciso/corretto :-D , chiedo aiuto con questa:

\( \ T (n) = 4T (n/2) + n^2 log n \)

Col Master non si riesce poiché non trovo un Epsilon per cui "domino chiaramente al di sopra" e manco qualcosa che domina inferiormente... [-X
Che supposizione posso fare per risolverlo? Non mi viene il cosidetto "sparare la GUESS"....
Giova411
Advanced Member
Advanced Member
 
Messaggio: 1603 di 2254
Iscritto il: 16/11/2006, 00:34


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite