Equazione di ricorrenza

[Darèios89]

Ho dei dubbi con delle equazioni di ricorrenza, qualcuno di voi saprebbe aiutarmi?

\( \displaystyle T(n)=5T(n/5)+n \log n \)
Io ho pensato:

\( \displaystyle \log n=m <-->2^m=n \)
\( \displaystyle T(2^m)=5T(2^m/5)+2^m/m \)
\( \displaystyle \frac{T(2^m)}{2^m}=\frac{5T(\frac{2^m}{5})}{2^m}+\frac{1}{m} \)
\( \displaystyle S(m)=\frac{T(2^m)}{2^m} \)
S(m)=5S(m/5)+1/m

Ora dovrei potere applicare qualcuno dei casi del teorema Master, ho pensato....il secondo.
Come soluzione avrei \( \displaystyle T(n)=m^{\log_{5}5}\logm=m\logm \)
\( \displaystyle T(n)=\log n \log \log n \)

Sono molto dubbioso...sono alle prime armi.

Poi avrei:

\( \displaystyle T(n)=4T(n/2)+n^2 \)
Dovrei potere applicare il teorema Master, ho scelto il secondo caso concludendo che la soluzione sia:
\( \displaystyle T(n)=n^2\logn \)


E infine due che dovrebbero risolversi con il Telescoping:
\( \displaystyle T(n)=T(n-1) + 1/n \) e l'altra
\( \displaystyle T(n)=T(n-1) + \log n \)

Su queste sono molto dubbioso, la prima dovrebbe diventare:

\( \displaystyle \sum_{i=1}^{n}f(i)=\frac{1}{i} \)

Come lo calcolo?
Sulla seconda mi blocco allo stesso punto.

[mod="Raptorista"]
Ho modificato le formule cambiando i log in \log per renderlo più leggibile. spero di non aver sbagliato a modificare
[/mod]

[hamming_burst]

Ciao,
allora ho provato a fare le prime due.
Sarebbero utili le condizioni di terminazione, ma non fa niente.

Per la seconda è perfetta per usare il Master Theorem, ho controllato il tuo risultato è corretto. Ricordati però di segnare anche il tipo di limitazione asintotica, in questo caso $\Theta(n^2*logn)$

Per la prima,è un po' sottile trovare una limitazione superiore, per quella inferiore si riesce anche a trovare una molto stretta, ma superiore c'è sempre un fattore $b$ che non torna. Per induzione e per sostituzione con il metodo dell'albero si trova una limitazione inferiore di $\Omega(n)$, non scrivo nulla perchè non penso ti interessi una dimostrazione di limitazione di questo tipo (se no basta dirlo). La tua soluzione mi sembra molto strana, con i miei conti non tornerebbe proprio. Baste che pensi comunque ad un algoritmo reale per capire che l'equazione di riccorrenza con quella complessità è piuttosto assurda (sempre che i miei conti di limitazione inferiore siano giusti), prova a pensare all'algoritmo della ricerca interpolata che ha una complessità simile. Domani voglio provare un'altra strada, per la limitazione superiore.

Le ultime due devi proprio utilizzare questa tecnica che chiami Telescoping, che non conosco, se no ci sono altre strade.

Potresti dirmi cos'è il Telescoping, che sono curioso.

Ciao, spero sia utile

[Darèios89]

Grazie dell'aiuto, sono contento di avere fatto bene quella con il teorema Master

Per le ultime, il telescoping è una tecnica per risolvere le equazioni del tipo:

T(n)=T(n-1)+f(n)

E la soluzione sarà data dalla sommatoria per i che va da 0 di f(i).
Quindi se avessi:


\( \displaystyle T(n)=T(n-1)+n \)

Calcolando la sommatoria avrei la funzione lineare, quindi la sommatoria diventerebbe la somma di n numeri naturali ovvero Gauss e la soluzione sarebbe:

\( \displaystyle T(n)=\frac{n(n+1)}{2} \)

Però mi confonde nei due casi specifici...

[hamming_burst]

Ciao,
scusa il ritardo non ho avuto tempo di rivedere la prima equazione, come promesso ho provato (e riprovato) ecco una possibile soluzione che mi ha fatto un attimo sudare:

Studio dell'equazione con l'albero di ricorsione (con gli altri non riesco a vedere nulla di positivo):

premessa per comodità uso $log_5$ al posto del consueto $log_2$ al massimo basta usare il cambio di base dividendo per $log_2(5)$

Codice:

$0$                    $n/logn$                             $(5^0)n/logn$

$1$               $(n/5)/(log(n/5))$   $(n/5)/(log(n/5))$ ....   $(n/5)/(log(n/5))$          $(5^1)*1/(5^1)*n/((logn)-(log5)) = n/((logn)-1)$



$logn-1$                  .........                   $(5^((logn)-1))*(1/(5^((logn)-1))) * n/((logn) - k)$

$logn   $      $T(1)$       $T(1)   $ ....      $T(1)   $             $5^logn = n$

calcolo la sommatoria fino al livello dell'albero $h-1$


$sum_{k=0}^((logn)-1) n/((logn) - k) = n*sum_{k=0}^((logn)-1) 1/(logn - k)$

questa sommatoria non riuscivo proprio a risolverla (pensavo fosse sbagliata), mi era familiare da un altro corso, ma proprio nn mi veniva in mente.
Cercando in vecchi appunti, mi ha illuminato un esercizio che citava l'n-esimo numero armonico.

Ricercando in internet ho trovato questo simpatico file:

http://www.dis.uniroma1.it/~ausiello/In ... RM/es7.pdf pag. 3

se questa sommatoria la mettiamo in questo modo:


$n*sum_{k=0}^((logn)-1) 1/(logn - k) = n*sum_{k=1}^logn 1/k = n*H_logn$

$H_logn <= loglogn + gamma <= loglogn + O(1)$ perchè $gamma$ è la costante (di Eulero) perciò $n*H_logn <= n*loglogn + O(1)$

perciò il livello $h-1 rArr nloglogn + O(1)$

sommando tutti i livelli dell'albero

$T(n) = n + nloglogn + O(1) in O(nloglogn)$ per proprietà della somma delle complessità


secondo me può essere corretta questa complessità, perchè: cercando nell'altro post una limitazione con il metodo dei tentativi,
la limitazione discostava sempre di un fattore $b$ minore di molte limitazioni standard e che non trovavo, perciò se questa soluzione
è "sbagliata" discosta di poco da quella corretta perchè una limitazione superiore più ampia che avevo provato era $O(nlogn)$ che non funzionava.





Per il Telescoping grazie della spiegazione, penso che questo metodo sia una generalizzazione delle "Ricorrenze lineari di ordine costante", un metodo come il Master Theorem che è una generalizzazione delle "Ricorrenze lineari con partizione bilanciata".
Proverò un altro giorno le altre due equazioni, per adesso mi è bastata la prima






Cmq ti ringrazio mi hai fatto ripassare i vari metodi di analisi delle complessità

Ciao, spero sia utile.

[Darèios89]

Ti ringrazio tantissimo!!!
Stasera sono cotto...quindi non sto guardando le soluzioni, domani mattina ridò un occhiata fresco fresco dal letto
Ma hai anche tu tra le materie da dare algoritmi?
Ti ringrazio tantissimo della gentilezza.

[hamming_burst]

Di nulla, mi piace questa parte di informatica, perciò volevo ripassarla.
No l'esame di algoritmi 1 lo ho già dato, ma sono arruginito sulla parte di analisi degli algoritmi (ora meno), al momento sto seguendo algoritmi avanzati.


Comunque ho risolto anche gli altri due, ma uno vorrei che lo risolvessi te e fai vedere la risoluzione, se no è troppo facile ricevere le risposte
non usare quello che chiami "telescoping" vai di albero di ricorsione che è un aiuto mentale fantastico, che alla fine ritrovi la stessa serie anche in questo modo.


per questa equazione $T(n) = T(n-1) + logn$

albero da un solo ramo (in orizzontale):

$ logn -> log(n-1) -> log(n-2) -> .......... -> log(n-k) $

$T(1)$ viene quando $k = n$

perciò altezza dell'albero $n$ sommando tutti i nodi viene $sum_{k=0}^(n-1) log(n-k)$

che viene $sum_{k=0}^(n-1) log(n-k) = sum_{h=1}^(n) logh = log(n!) <= nlogn rArr O(nlogn)$

per capire perchè questa limitazione vedi qua:

https://www.matematicamente.it/forum/ser ... 65443.html

su un mio libro ho trovato anche una limitazione migliore cioè vale $log(n!) in Theta(nlogn)$
che è di facile dimostrazione basta che vedi che vale la limitazione inferiore $Omega(nlogn)$ dimostrandolo per induzione su $(n/2)^(n/2) <= n!$ (questo per via che nel fattoriale si cono $n/2$ terrmini maggiori o uguali di $n/2$) dal link che ti ho messo è dimostrato che $n! <= n^n$


perciò $(n/2)^(n/2) <= n! <= n^n$ applicando il logaritmo $(n/2)log(n/2) <= log(n!) <= nlogn$

dicendo che $(n/2)log(n/2) = 1/2n*(logn - log2) = 1/2n*(logn -1 ) <= log(n!)$ con $n>2$

$1/2nlogn - 1/2n <= 1/2nlogn <= log(n!)$

perciò per differenza di una costante è dimostrato (meglio che controlli i conti, ma a me sembrano corretti) $c*nlogn <= log(n!) <= c*nlogn rArr log(n!) in Theta(nlogn)$


L'altro prova te, è semplice se guardi le due risoluzioni che ho scritto.

Ciao

[Darèios89]

Per \( \displaystyle T(n)=T(n-1)+1/n \)

Mi viene da usare solo il telescoping......e ottengo la sommatoria per i che va da 0 a n di f(i).
Passando all' integrale dovrei avere

\( \displaystyle \int\frac{1}{n} \) viene logn.
Quindi il risultato dovrebbe essere \( \displaystyle T(n)=\theta(logn) \)

[hamming_burst]

Perfetto corretto

usando l'albero di ricorsione mi risulta uguale.
Questo Telescoping devo proprio recuperarmelo, se riesci a risolverlo solo in questo modo vuol dire che è molto potente come il Master Theorem.

se ne hai altri e vuoi na mano, posta pure. Ciao


@Rapstoria:
Solo una cosa, nelle modifica della funzione $T(n)=m^(log_{5}5)=m$ dovrebbe essere $T(n)=m^(log_{5}5)*logm=m*logm $
cioè anche se hai modificato non viene visualizzato il $logn$ (almeno io non lo vedo), se no non si capisce "l'errore". Forse prova mettendo un simbolo di moltiplicazione tra le variabili