Ricorrenza bellina con sostituzione [Risolto APA!]
Eccoci che pensavo di farcela ma non riesco a concludere:
$ T(n) = 5T(n/5) + n/(log n) $
Ho pensato che, siccome divido per 5, ho un logaritmo in base 5.
Poniamo $ n = 5^m $ quindi $ m = log_5 n $
$ T(5^m) = 5T(5^m / 5 ) + 5^m/(log_5 5^m) = 5T(5^m/5) + 5^m/m $
Eccoci...
$S(m) = T(5^m) = 5S(m-1) + $ ?!
$ T(n) = 5T(n/5) + n/(log n) $
Ho pensato che, siccome divido per 5, ho un logaritmo in base 5.
Poniamo $ n = 5^m $ quindi $ m = log_5 n $
$ T(5^m) = 5T(5^m / 5 ) + 5^m/(log_5 5^m) = 5T(5^m/5) + 5^m/m $
Eccoci...
$S(m) = T(5^m) = 5S(m-1) + $ ?!
Risposte
Bhe.. Direi che devi scrivere \(5^m/m\).. Che dubbi hai?
Sì Apa avevo pensato di andare normalmente ma non arrivo alla soluzione che dovrebbe essere $O(n log(log n) ) $
Per normalmente intendo che forse c'é qualche teorema che non so per queste ricorrenze.
Cmq sul Cormen nulla trovo se non sostituzione di variabile...
Per normalmente intendo che forse c'é qualche teorema che non so per queste ricorrenze.
Cmq sul Cormen nulla trovo se non sostituzione di variabile...
Ah, ok.. Pensavo che il problema fosse che non sapevi come terminare quel passaggio. Se vai avanti con i tuoi calcoli ottieni che
\[ S(m) = 5\,S(m-1) + \frac{5^m}{m} = \frac{5^m}{m} + 5\,\left( \frac{5^{m-1}}{m-1} + 5\,\left( \frac{5^{m-2}}{m-2} + \dots \right) \right) = 5^m \, \sum_{i=1}^{m} \frac{1}{i} = n \, \sum_{i=1}^{\log_5(n)} \frac{1}{i} \]
E ora non dovrebbe essere difficile concludere..
\[ S(m) = 5\,S(m-1) + \frac{5^m}{m} = \frac{5^m}{m} + 5\,\left( \frac{5^{m-1}}{m-1} + 5\,\left( \frac{5^{m-2}}{m-2} + \dots \right) \right) = 5^m \, \sum_{i=1}^{m} \frac{1}{i} = n \, \sum_{i=1}^{\log_5(n)} \frac{1}{i} \]
E ora non dovrebbe essere difficile concludere..
"apatriarca":
Ah, ok.. Pensavo che il problema fosse che non sapevi come terminare quel passaggio..
Sì, in quel momento era insicuro anche in quello, son sincero
GRAZIE COME SEMPRE
"apatriarca":
E ora non dovrebbe essere difficile concludere..
Giusto per tenerti aggiornato... Non ho concluso mica!!!
Non la sbroglio la situazione pur sapendo la soluzione!!!
(Che vergogna!!!)
Quanto vale quella serie che ho scritto? Il mio consiglio è quello di confrontare quella serie con il corrispondente integrale se non hai idea di come risolverla.
Ok mi sono tirato la zappa sui piedi!!! Sono uscito fuori programma visto che non chiede cose così difficili.
Non ricordo una mazza con gli integrali, stavo cercando difatti.
Ero fermo sulla somma di potenze che mi porta semplicemente a
$(n(n-1) )/ 2$ partendo da $\sum_{i=1}^{\n) i$
Ho pensato di capovolgere il tutto e sono andato a cucinare alla nonna felice!!!
(ma facevo finta di averla risolta a quanto pare =)
Non ricordo una mazza con gli integrali, stavo cercando difatti.
Ero fermo sulla somma di potenze che mi porta semplicemente a
$(n(n-1) )/ 2$ partendo da $\sum_{i=1}^{\n) i$
Ho pensato di capovolgere il tutto e sono andato a cucinare alla nonna felice!!!
(ma facevo finta di averla risolta a quanto pare =)
L'idea è quella di osservare che
\[ \sum_{i=1}^n \frac{1}{i} = \sum_{i=1}^n \frac{1}{i} \int_{i}^{i+1} dx > \int_{1}^{n+1} \frac{dx}{x}. \]
Infatti \(1/x \le 1/i\) nell'intervallo \([i, i+1]\). Siccome a questo punto sai che
\[ \int_1^{n+1} \frac{dx}{x} = \ln(n+1) \]
Puoi concludere che
\[ \sum_{i=1}^n \frac{1}{i} \in \Omega(\log(n)). \]
Osservando inoltre che
\[ \sum_{i=1}^n \frac{1}{i} = 1 + \sum_{i=2}^n \frac{1}{i} \int_{i-1}^{i} dx < 1 + \int_{1}^{n} \frac{dx}{x} \]
puoi invece dedurre che
\[ \sum_{i=1}^n \frac{1}{i} \in O(\log(n)) \]
e quindi anche
\[ \sum_{i=1}^n \frac{1}{i} \in \Theta(\log(n)). \]
\[ \sum_{i=1}^n \frac{1}{i} = \sum_{i=1}^n \frac{1}{i} \int_{i}^{i+1} dx > \int_{1}^{n+1} \frac{dx}{x}. \]
Infatti \(1/x \le 1/i\) nell'intervallo \([i, i+1]\). Siccome a questo punto sai che
\[ \int_1^{n+1} \frac{dx}{x} = \ln(n+1) \]
Puoi concludere che
\[ \sum_{i=1}^n \frac{1}{i} \in \Omega(\log(n)). \]
Osservando inoltre che
\[ \sum_{i=1}^n \frac{1}{i} = 1 + \sum_{i=2}^n \frac{1}{i} \int_{i-1}^{i} dx < 1 + \int_{1}^{n} \frac{dx}{x} \]
puoi invece dedurre che
\[ \sum_{i=1}^n \frac{1}{i} \in O(\log(n)) \]
e quindi anche
\[ \sum_{i=1}^n \frac{1}{i} \in \Theta(\log(n)). \]
[size=200]A P A T R I A R C A [/size]
Nota che ti ho scritto tutti i passaggi, ma in pratica c'è un teorema più generale che permetteva di concludere direttamente senza scrivere tutte quelle cose. Ma siccome non penso tu l'abbia visto ho pensato di mostrarti i vari passaggi necessari per una dimostrazione di questo tipo.
Grazie Apa.
Difatti non l'ho mai visto e "penso/spero" non l'abbiano fatto nel corso mio.
Di teoremi ho:
Master T, teoremi per ricorrenze lineari con partizione bilanciata e ricorrenze lineari di ordine costante.
Quest'ultimo forse qualcosa diceva...
Difatti non l'ho mai visto e "penso/spero" non l'abbiano fatto nel corso mio.
Di teoremi ho:
Master T, teoremi per ricorrenze lineari con partizione bilanciata e ricorrenze lineari di ordine costante.
Quest'ultimo forse qualcosa diceva...
Apa ma alla fin fine è solo
$\Theta(\n log_5(n))$
e non $\Theta(\n log_5(log_5(n)))$
Che bordello!!!
$\Theta(\n log_5(n))$
e non $\Theta(\n log_5(log_5(n)))$
Che bordello!!!
No, guarda bene.. nel tuo caso hai che quella serie che ho scritto arriva fino a \(\log(n)\) e non \(n\).. Per cui si arriva alla conclusione corretta..
Ovvio sì!!! Mi ero perso qualche indice!!!!
Inizio a costruirti una statua
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo