Complessità computazionale - Teoria

L’algoritmo di ricerca lineare considera uno dopo l’altro tutti i valori contenuti negli elementi dell’array fino a trovare un elemento contenente il valore cercato oppure fino ad arrivare alla fine dell’array senza aver trovato il valore cercato. Nel caso pessimo la complessità cresce quindi linearmente rispetto al numero di elementi dell’array.
L’algoritmo di ricerca binaria richiede che l’array sia stato preventivamente ordinato e in virtù di questo riesce a dimezzare ad ogni passo lo spazio di ricerca. Infatti, l’algoritmo confronta il valore cercato con quello contenuto nell’elemento che occupa la posizione centrale dell’array. Se i due valori sono diversi, la ricerca continua solo nella metà sinistra o solo nella metà destra dell’array a seconda che il valore cercato sia minore o maggiore di quello con cui è stato confrontato. Nel caso pessimo la complessità cresce quindi logaritmicamente rispetto al numero di elementi dell’array.
Nel caso peggiore:
Ricerca sequenziale: T(n) = O(n)
Ricerca binaria: T(n) = log2n

Calcolo del tempo di esecuzione di un algoritmo
Ciò che interessa nello studio della complessità asintotica di un algoritmo non è tanto il tempo di esecuzione per un particolare valore di n della dimensione dell’input, ma piuttosto dalle modalità con cui tale tempo cresce al crescere di n.
Notazione O (“grande”)
“un criterio matematico per partizionare gli algoritmi in classi di complessità”
Una funzione g(n) si dice che è un O-grande di una funzione h(n) e si scrive
g(n)=O(h(n))
se esistono due constanti positive c e n0 tali che per ogni n³ n0 risulta
g(n)

Un algoritmo la cui complessità in tempo T(n) è O(g(n)) è detto avere complessità asintotica in tempo, o velocità di crescita, g(n).
Esempi di complessità asintotiche
Costante: T(n)=O(1)
Il tempo di esecuzione dell’algoritmo è indipendente dall’input.
Logaritmica: T(n)=O(log n)
E’ tra i migliori tassi di crescita
Polinomiale: T(n)=nk
Esponenziale: T(n)=O(an) con a>1
Definizioni
· Un problema è detto computabile quando esiste un algoritmo che lo risolve.
· I problemi il cui algoritmo risolutivo possiede un andamento esponenziale sono di fatto non risolvibili (Problemi intrattabili)
· Un problema è effettivamente computabile, cioè è risolvibile con un calcolatore in un tempo accettabile, se è risolto da un algoritmo con complessità in tempo di tipo polinomiale.