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
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
