Pages: [1]   Go Down
Print
Author Topic: Esercizio Eq. di Ricorrenze: Sostituzione di variabili  (Read 839 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
کtεvЭ
Matricola
*
Offline Offline

Gender: Male
Posts: 40



« on: 22-07-2013, 10:37:38 »

Qualcuno potrebbe perfavore spiegarmi come risolvere questo esercizio?
(Esercizi Problema 4.4 http://www.dmi.unict.it/~cutello/ricorrenza.pdf)

T(n)=5T(\frac{n}{5})+\frac{n}{log n}

Il testo suggerisce di usare la sostituzione di variabili con   n = 5^m
Logged

<< Poco importano le note in musica, contano le sensazioni che esse producono >> .
Turing
Matricola
*
Offline Offline

Gender: Male
Posts: 22



« Reply #1 on: 22-07-2013, 15:03:10 »

poni n=5^m

ne segue ke m=log n  (a meno di una costante, ke trascuriamo)

quindi l'equazione diventa:

T(5^m) = 5 T(5^(m)/5) + (5^m)/m
T(5^m) = 5 T(5^(m-1)) + (5^m)/m

dividendo tutto per 5^m si ottiene

T(5^m)/(5^m) =  T(5^(m-1))/(5^m) + 1/m     ----------------> S(m)= T(5^m)/(5^m)   ***


S(m) = S(m-1) + 1/m

che si risolve banalmente col telescoping ===> S(m)= O(log m) ===>S(m)<= c * log m

noi sappiamo che  T(5^m) = S(m) * 5^m

e quindi T(n)<=c * log m * 5^m      con m=log n si avrà

T(n)<=c * log log n * n -----------> T(n)= O(n log log n)


spero sia giusto.... e scusa per come l'ho scritto.... il tex mi dava problemi strani XD
Logged
کtεvЭ
Matricola
*
Offline Offline

Gender: Male
Posts: 40



« Reply #2 on: 23-07-2013, 09:12:36 »

grazie mille  ok
Logged

<< Poco importano le note in musica, contano le sensazioni che esse producono >> .
Pages: [1]   Go Up
Print
Jump to: