Salve a tutti. Ho svolto questo esercizio sulla complessità computazionale. Per verificare che sia corretto come dovrei fare? Grazie mille
Mostrare la relazione di ricorrenza che descrive il costo computazionale
(in termini di numero di operazioni richieste) del seguente algoritmo,
mostra come calcolare il tempo di esecuzione partendo da tale ricorrenza,
ed infine indicare il tempo di esecuzione. Si consideri unicamente
il caso pessimo.
Int MyFunc(int a[], int n)
{
if (n==0) return 0;
if (n==1) return a[0];
int ret1 = MyFunc(a,n/2);
int ret2 = MyFunc(a+n/2,n-n/2);
return ret1+ret2;
}
il caso peggiore (worst case) che corrisponde a quelle (o a quella) configurazioni
della struttura dati d che corrispondono a un massimo del tempo (sempre fissato
un valore di n)
Equazione di ricorrenza
T(n) = c1 per n = 0 e n = 1
T(n) ) 2T(n/2)+c2
T(n) appartenente $ in O(nlog_2(n)) $
T(n) = 2T(n/2) + nc2 = 2[2T(n/4)+n/2c2]+nc2 = 4T(n/4)+2c2n = ... =
= 2^iT(n/2^i)+ic2n= ... = nc1 + c2nlog(n) = O(nlog(n))
per n = 2^i <=> i = log_2(n)