complessità computazionale

[giacomovicinanza]

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.

Codice:

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)) $

Codice:

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)

[Quinzio]

Salve a tutti. Ho svolto questo esercizio sulla complessità computazionale. Per verificare che sia corretto come dovrei fare?

Verificare questi esercizi e' relativamente semplice: fai un programmino che implementa la tua funzione e lo fai girare.
E in qualche modo misuri il tempo che serve a terminare le iterazioni.

L'ho fatto io per te, anche perche' ero curioso di provare. Non l'avevo mai fatto neanche io.
L'immagine sotto e' il risultato.

Sulle ascisse c'e' il parametro n in migliaia, in ordinata c'e' il tempo in microsecondi.
La linea fatta dai "puntini" blu sono i dati reali.
La linea piu' regolare rossa e' la funzione $1.5/1000 \ n\ \ln(n/1000)$.
Ci sono dei punti "anomali" perche' puo' accadere che ogni tanto il processore viene interrotto per fare dei task lunghi e quindi va in stallo per qualche tempo.

Come vedi piu' o meno i dati reali battono pari con la formula.
La $n\ log(n)$ sostanzialmente e' la stessa cosa di una funzione lineare.
I dati reali sembrano essere davvero una funzione lineare, ma direi che ci sono altri effetti da tenere conto, il tuo risultato e' corretto.

Codice:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

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;
}

int main(void) {
   clock_t t1, t0;
   int a[1000000];
   long tta[1000000];
   CLOCKS_PER_SEC;
   for (long var = 0; var < 1000000; var+=1000) {
      t0 = clock();
      MyFunc(a, var);
      t1 = clock();
      printf("%d\n", t1-t0);
   }

   return EXIT_SUCCESS;
}

[giacomovicinanza]

Grazie mille

[apatriarca]

Prima di tutto credo sia importante osservare che nel tuo caso il tempo di esecuzione non dipende dai valori di input (solo dalla sua dimensione). È importante perché si chiede di considerare il caso peggiore, per cui nel tuo programma dovresti assicurarti di generarlo.

La tua soluzione non è inoltre corretta. Hai infatti aggiunto un \(n\) nella soluzione della ricorrenza che non era presente nella ricorrenza originale. La tua soluzione avrebbe dovuto essere:
\[
\begin{align*}
T(n) &= 2\,T(n/2) + C_2 \\
&= 2(2\,T(n/4) + C_2) + C_2 \\
&= 4\,T(n/4) + 3\,C_2 \\
&= \dots \\
&= 2^i\,T(n/2^i) + C_2\,\sum_{j=0}^{i-1} 2^j \\
&\approx n\,C_1 + (n - 1)\,C_2 \quad (n \approx 2^i) \\
&= \Theta(n).
\end{align*}
\]

Esistono diversi tipi di verifiche sulla correttezza della tua soluzione. La prima consiste semplicemente nel verificare ogni passaggio della tua soluzione o usare un metodo diverso per risolvere la ricorrenza. Per verificare la ricorrenza puoi contare il numero di operazioni in qualche caso semplice (per esempio per input di 2, 4, 8, 16 valori) e contare il numero di operazioni vedendo se la ricorrenza fornisce i valori corretti. Nel tuo caso hai che (contando i \(+\) e quindi con \(C_1 = 0\) e \(C_2 = 1\)) hai che:
\[ T(2) = 1, \quad T(4) = 3, \quad T(8) = 7, \quad T(16) = 15 \]
Puoi infine calcolare il tempo di esecuzione. Il problema principale di questo metodo è che il tempo di esecuzione dipende da diversi fattori che non sono necessariamente sotto il tuo controllo e che alcuni grafici sono abbastanza simili tra di loro. Un buon grafico mostra di solito che i punti si avvicinano sempre di più alla curva con l'aumentare di \(n\). Il grafico di Quinzio non mostra questo comportamento.

[giacomovicinanza]

Grazie mille