Introduzione

La complessità computazionale si occupa della valutazione del costo degli algoritmi in termini di risorse di calcolo (principalmente tempo di elaborazione e quantità di memoria utilizzata). L'obiettivo è quello di comprendere le prestazione massime raggiungibili da un algoritmo applicato ad un determinato problema computazionale.

Prefazione[modifica | modifica wikitesto]

Problema computazionale[modifica | modifica wikitesto]

Dato un dominio di input e un dominio di output, un problema computazionale è rappresentato dalla relazione matematica che associa un elemento del dominio di output ad ogni elemento del dominio di input.

Algoritmo[modifica | modifica wikitesto]

Dato un problema computazionale, un algoritmo è un procedimento effettivo che risolve il problema in tempo finito, espresso tramite un numero definito di passi elementari ben specificati in un sistema formale di calcolo.

Modello di Calcolo e di costo[modifica | modifica wikitesto]

Il modello di calcolo che utilizzeremo per analizzare gli algoritmi è il cosiddetto Random Access machine(RAM). Questo modello contiene istruzioni che si trovano comunemente nei computer reali: istruzioni aritmetiche,istruzioni di assegnamento, istruzioni di input e output, accesso ad un elemento qualsiasi di un vettore, valutazione di un’espressione booleana, istruzioni per spostare i dati e istruzioni di controllo. Ciascuno di queste istruzioni (chiamate anche passi base) richiede una quantità costante di tempo.

Nel modello RAM non tenteremo di modellare la struttura gerarchica della memoria che comune di computer reali, ovvero non invieremo la memoria cache ho la memoria virtuale.

Analizzare gli Algoritmi[modifica | modifica wikitesto]

Quello che spesso si usa per analizzare un algoritmo è il tempo di esecuzione. Il tempo di esecuzione di un algoritmo per un particolare input è il numero di operazioni primitive che vengono eseguite o passi base.

Quindi il tempo di esecuzione non è altro che la somma di tempi di esecuzione per ogni istruzione.

Ecco un banale esempio:

Calcolo-passi-base.jpg
Esempio    esempio calcolo passi base per l'algoritmo insertion sort  

Un altro esempio di calcolo dei passi base per l'algoritmo di ordinamento Insertion Sort.

Per calcolare T(n) (tempo di esecuzione di Insertion Sort) sommiamo i prodotti delle colonne costo e numero di volte, ottenendo:

Anche per più input della stessa dimensione, il tempo di esecuzione di un algoritmo può dipendere da quale input di quella dimensione viene scelto. Per esempio, insertion Sort il caso migliore si verifica se l’array è già ordinato. Quindi il tempo di esecuzione nel caso migliore diventa:

Best-case-insertion-sort.jpg

Questo tempo di esecuzione può essere espresso con me an + b, con Le costanti a e b che dipendono dei costi dell'Istruzione c; quindi è una funzione lineare di n.

Se l'array è ordinato nel senso inverso allora si verifica il caso peggiore. Il tempo di esecuzione di insertion Sort nel caso peggiore è:

Worst-case-inserion-sort.jpg

Questo tempo di esecuzione può essere espresso come an² + bn + c, con Le costanti a,b e c che dipendono i costi dei costi delle istruzioni dei casi base c, quindi è una funzione quadratica di n.



Caso migliore, medio e peggiore[modifica | modifica wikitesto]

Nell'analisi degli algoritmi possiamo avere diversi casi in base al tipo di input che abbiamo. Ad esempio in un algoritmo di inserion-sort il caso migliore è il caso in cui l'algoritmo risulta essere già ordinato, il caso peggiore è il caso in cui l’array è ordinato alla rovescia, mentre il caso medio è il caso intermedio tra il migliore e il peggiore. Per determinare il tempo di esecuzione di un algoritmo si utilizzerà nella maggior parte dei casi il tempo di esecuzione nel caso peggiore dato che:

  • il tempo di esecuzione del caso peggiore è il limite superiore al tempo di esecuzione di qualsiasi input.
  • per alcuni algoritmi il caso peggiore si verifica molto spesso.
  • il caso "medio" è spesso cattivo quasi quanto quello peggiore.

Tasso di crescita[modifica | modifica wikitesto]

Un'ulteriore semplificazione che attueremo, per quanto riguarda il tempo di esecuzione di un algoritmo, è quella di è quello di osservare quello che è il suo tasso di crescita. Di conseguenza considereremo soltanto il termine principale di una formula in quanto i termini di ordine inferiore sono relativamente insignificanti per valori grandi di n. Ignoriamo anche il coefficiente costante del termine principale.

Successivo