Costo computazionale

Per il calcolo del costo computazionale siamo interessati a calcolare le operazioni elementari, ovvero gli assegnamenti e le operazioni logico-aritmetiche, eseguite durante l’esecuzione di un algoritmo.

Analisi del caso peggiore

È l’analisi più importante, perché restituisce un limite superiore per una qualsiasi istanza di input. Si cerca ovviamente la funzione più piccola possibile.

Analisi del caso medio

È solitamente difficile da individuare, e restituisce la distribuzione delle istanze di input.

Analisi del caso migliore

È poco significativa, e restituisce un limite inferiore per una qualsiasi istanza di input. Si può anche dire che è il limite superiore per una sola istanza di input.

Costo computazionale di algoritmi

Basandosi sulle notazioni asintotiche, si ha che:

• $O(f(n))$: per nessun input, l’algoritmo costa più di $f(n)$ L’upper bound indica il costo computazionale del miglior algoritmo noto per il problema.
• $\Omega (f(n))$: per tutti gli input l’algoritmo costa almeno $f(n)$ Il lower bound indica che nessun algoritmo per il problema può costare meno di $f(n)$.
• $\Theta (f(n))$: per tutti gli input l’algoritmo costa $f(n)$ Il tight bound indica che esiste un algoritmo ottimo per il problema.

La difficoltà dei problemi si basa sul fatto di essere o meno in grado di trovare un algoritmo efficiente per il problema.

I problemi si possono classificare per difficoltà:

• problemi trattabili - facili. Esiste un algoritmo per il problema di costo computazionale polinomiale ($T(n)\in O(n^k),k\ge 0$)
• problemi presumibilmente intrattabili - difficili. Non c’è un algoritmo di costo polinomiale, ma non è dato dimostrato che non esiste.
• problemi intrattabili. Si può dimostrare che non esiste un algoritmo per il problema di costo polinomiale.
• problemi irrisolvibili. Si può dimostrare che non esiste un algoritmo per il problema, indipendentemente dal costo.

Calcolo del costo

Esempio 1

for i:=0 to n-1
	c := c+1
	d := d+1
c := c+d

$T(n)$ è il numero massimo di operazioni eseguito dalla porzione di codice in funzione di $n$. Si deve trovare $f(n)$ più piccola possibile tale che $T(n)\in O(f(n))$.

c := c+1 e d := d+1 contengono 2 operazioni ciascuna, perché entrambe hanno un’operazione aritmetica, e un’operazione di assegnamento.

Il ciclo for i := 0 to n-1 viene eseguito $n$ volte, quindi le operazioni totali contenute nel ciclo sono $4n$.

L’ultima riga, ovvero c := c+d, contiene anch’essa, come le due sopra, 2 operazioni.

In totale questo algoritmo esegue $4n+2$ operazioni. Quindi $T(n)=4n+2\in O(n)$, ed è quindi un costo lineare.

Esempio 2

for i=0 to n-1
	for j=i to n-1
		x := x+1
	y := y+1

x := x+1 contiene 2 operazioni.

Il ciclo for j=i to n-1, fissato i, viene eseguito n-i volte. Viene eseguito la prima volta quando j=i, e l’ultima quando j=n-1, ovvero $(n-1)-i+1=n-i$.

Per il ciclo più esterno si ha:

• i=0 $\to 2\cdot n$ operazioni +
• i=1 $\to 2\cdot (n-1)$ operazioni +
• i=2 $\to 2\cdot (n-2)$ operazioni +
• …
• i=(n-2) $\to 2\cdot (n-(n-2))=2\cdot 2$ operazioni +
• i=(n-1) $\to 2\cdot (n-(n-1))=2\cdot 1$ operazioni

$=2\cdot (n+(n-1)+(n-2)+...+2+1)=2{\sum }_{i=1}^{n}i=2\frac{n(n+1)}{2}=n(n+1)$

Il ciclo esterno viene eseguito n volte, e quindi l’assegnazione y := y+1 viene eseguita n volte, quindi le operazioni totali sono $2\cdot n$.

In totale quindi si ha $T(n)=n(n+1)+2n=n^2+3n\in O(n^2)$, che è un costo quadratico.

Esempio 3

x := 0
y := 1
while y < n+1
	x := x+1
	y := 2y
return x

Gli assegnamenti prima del while hanno costo $O(1)$, e anche all’interno del while gli assegnamenti hanno costo $O(1)$.

$y=1$. Dopo la prima iterazione $y=2$. Dopo la seconda iterazione $y=2^2$. Dopo la terza si ha $y=2^3$. Dopo la i-esima iterazione si ha $y=2^i$.

Dopo quando si ha che $2^{k+1}=y>n+1>2^k$? Ovvero, quando si ha vero $n\ge 2^k$? Quando $\log n\ge k$.

In sostanza, si ha che $T(n)\in O(\log n)$, ovvero ha un costo logaritmico.

asd_08