[algoritmi] equazioni di ricorrenza

[querty-votailprof]

salve,

ho un problema con questa equazione di ricorrenza

T(n)= 2T(n/5) + T(n/2)+n

io la risolvo con l'albero e poi il costo viene O(n)
perchè ad ogni livello costa $9n/10$ la formula è

$n\sum_{i=0}^\log n\ (9/10) ^i $

ma il professore dice che il costo è n log n

ma non capisco il motivo..

[apatriarca]

Mostra i passaggi che hai fatto.

[querty-votailprof]

emmm dovrei disegnare, l'albero di ricorsione??

[querty-votailprof]

posso postare un'immagine?

[apatriarca]

Puoi inserire una immagine attraverso il suo URL (deve quindi insomma essere accessibile via internet*). Ma credo che si possa anche descrivere i tuoi passaggi attraverso delle formule e del testo.

Ho provato a calcolare quella ricorrenza per un po' di valori di \(n\) e cresce senza dubbio più velocemente di \(O(n)\). Non ho ancora avuto però il tempo di mettermi effettivamente a fare i calcoli per vedere che sia effettivamente come dice il tuo professore (suppongo che sia così).

* Esistono diversi siti che ti permettono di caricare gratuitamente le tue immagini con questo scopo.

[hamming_burst]

"quertymax":salve,

ho un problema con questa equazione di ricorrenza

T(n)= 2T(n/5) + T(n/2)+n

io la risolvo con l'albero e poi il costo viene O(n)
perchè ad ogni livello costa $9n/10$ la formula è

$n\sum_{i=0}^\log n\ (9/10) ^i $

ma il professore dice che il costo è n log n

ma non capisco il motivo..

$2^i(n/5^i) + n/2^i$ in forma generale.
Il cammino radice-foglia più lungo ha altezza $log_2(n)$

Quindi la sommatoria diviene (è uguale alla tua sommatoria...):

$sum_{i=0}^{log_2(n)-1}2^i n/5^i + n/2^i = n\sum_{i=0}^{log_2(n)-1}(2/5)^i + n\sum_{i=0}^{log_2(n)-1}(1/2)^i =$
$= n(1 - (2/5)^{log_2(n)})/(1 - (2/5)) + n(1 - (1/2)^{log_2(n)})/(1 - (1/2)) =$

$= 5/3n - 5/3n^(1+log_2(2/5)) + 2n - 2n^(1+log_2(1/2)) = 5/3n - 5/(3*n^0.32) + 2n - 2 \in O(n)$

anche contando le foglie non si arriva sopra $O(n)$

l'unica ipotesi che mi viene in mente, per giustificare la soluzione del tuo docente è che ha utilizzato qualche approssimazione oppure un metodo differente di risoluzione.
Se avesse utilizzato un'approssimazione, vedendo che $9/10 \approx 1$ (molto allegramente), ha arrotondato il costo per ogni livello dell'albero ha $1$ quindi ogni livello ha costo sempre uguale. Questo sarebbe giustificato dal fatto che i costi sono sproporzionati e si hanno dei "buchi" nei livelli più profondi dell'albero, nei rami derivanti da $n/2$ (perchè i rami derivanti da $n/5$ avrebbero già finito la ricorsione).

Quindi la sommatoria diviene $sum_{i=0}^{log_2(n)-1} n*1 \in O(nlog(n))$

[apatriarca]

Dal punto di vista teorico sono arrivato più o meno ai vostri stessi risultati. Non mi piace molto ricorrere ad una approssimazione del genere. Implementando però la ricorrenza si osserva come essa sia però certamente \(O(n\,\log(n))\). Il codice che ho usato è il seguente (python). L'ho scritto di fretta ma credo sia giusto.

from pylab import *
import numpy as np

N = np.arange(0, 100000)
T = np.zeros(100000)
for n in N[1:]:
	T[n] = 2.0*T[int(n/5.0)] + T[int(n/2.0)] + n
P = T[1:]/N[1:]
Q = P/np.log2(N[1:])

plot(N[1:], P, 'r-')
plot(N[1:], Q, 'b-')
xlabel('n')
ylabel('T(n)/n (red) and T(n)/n*log(n) (blue)')
grid(True)
savefig('test.png')
show()

L'immagine generata la si trova invece al seguente link: http://img5.imageshack.us/img5/9893/testdqr.png.

[hamming_burst]

mmm interessante analisi.

Ma per togliere ogni dubbio, basta dimostrare per induzione quale è la limitazione corretta.

ipotizziamo che per $n=1$ si abbia costo $O(1)$

$T(n) \in^? O(n)$

il caso base è ovvio.

$T(n) = 2T(n/5) + T(n/2) + n $
$<= 2cn/5 + cn/2 + n$
$= 9/10cn + n$
$= (9/10c + 1)n <= cn$

$\text{iff } c >= 10$

mi pare non si possa confutare questa limitazione più stretta, a meno di miei errori. A dir di più penso si possa anche dire che sia $\Theta(n)$ vedendo che il limite inferiore è banalmente dimostrabile esser $\Omega(n)$.

Per l'andamento delle funzioni date dal tuo codice, ora non saprei dare una spiegazione, se non per qualche approssimazione interna dei numeri che sballa la normalizzazione e che utilizzando il logaritmo in base $2$ sarebbe una "sovrastima" anche se quasi inesistente...bho

[apatriarca]

E' sempre possibile che il codice abbia preso in considerazione numeri troppo piccoli e che la curva rossa ad un certo punto tenda ad un valore finito. La prova sperimentale usando il codice e' pur sempre incapace di prevedere il comportamento della funzione per \(n \to \infty\). Si può provare ad aumentare il numero ad un milione e a vedere come si comporta. Tuttavia dubito che si vedrà qualcosa di completamente diverso da quello che già si vede. La funzione \(T(n)/n\) cresce infatti molto lentamente da quanto si può osservare ed è difficile capire se una funzione tende ad un limite finito oppure è semplicemente molto lenta guardando un grafico. Forse si può cercare di studiare \( T(n)/n \) o calcolare la serie in modo meno approssimato.

EDIT: Il grafico per \(n\) fino ad un milione è, come previsto, del tutto simile a quello precedente.