Complessità computazionale

Complessità computazionale

Complessità = risorse necessarie a risolvere un problema (tempo di calcolo, spazio ausiliario), non interessano valori assoluti che dipendono da una specifica macchina fisica e da specifici dati
Dimensione: caratteristiche dei dati dai quali dipende il consumo di risorse
Caso peggiore/migliore: configurazione che genera il peggiore/migliore consumo di risorse
Complessità in tempo/spazio: una stima della forma asintotica di come il tempo/spazio di calcolo variano in funzione della dimensione dei dati
Due forme di complessità:
- upper bound, limitazioni superiori: risorse usate da uno specifico algoritmo/programma: analisi di algoritmi/complessità concreta.
- lower bound, limitazioni inferiori: risorse necessarie per la soluzione di un problema: teoria della complessità.
- se le due analisi coincidono: un problema è classificato

Notazione o-grande
Usata per la notazione asintotica
Notazione o-grande: date due funzioni f e g (sotto ipotesi ragionevoli su f e g) dalla dimensione dei dati in n: f è o(g) sse esistono costanti c e b e un valore della dimensione n_0 tale che per ogni n>n_0 t.c. f(n)≤c*g(n)+b
Cioè f è definitivamente maggiorata da g a meno di costanti moltiplicative e additive
Tempo costante
Tempo logaritmico
Tempo lineare
Tempo log-lineare
Tempo polinomiale
Tempo esponenziale

Ordinamento (sorting)
Due possibilità diverse:
- creare una copia
- ordinare in place
Algoritmi naive:
- selection sort
- insertion sort
- bubble sort
- shell sort