Concetti Chiave
- La complessità computazionale si riferisce alle risorse necessarie per risolvere un problema, indipendentemente dalla macchina fisica o dai dati specifici.
- La complessità in tempo e spazio valuta come queste risorse variano asintoticamente rispetto alla dimensione dei dati.
- Le analisi della complessità includono il limite superiore (upper bound) e inferiore (lower bound), con la coincidenza di entrambi che indica la classificazione del problema.
- La notazione o-grande è utilizzata per descrivere il comportamento asintotico delle funzioni rispetto al consumo di risorse.
- Gli algoritmi di ordinamento possono essere implementati creando una copia dei dati o direttamente nella memoria originale, con esempi di algoritmi semplici come selection sort, insertion sort, e bubble sort.
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
Domande da interrogazione
- Qual è la differenza tra upper bound e lower bound nella complessità computazionale?
- Quali sono alcuni esempi di algoritmi di ordinamento naive?
L'upper bound rappresenta le limitazioni superiori delle risorse usate da uno specifico algoritmo, mentre il lower bound indica le risorse necessarie per risolvere un problema. Se le due analisi coincidono, il problema è classificato.
Alcuni esempi di algoritmi di ordinamento naive includono il selection sort, l'insertion sort, il bubble sort e lo shell sort. Questi algoritmi possono essere implementati creando una copia dei dati o ordinando in place.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
