Index
Introduzione
L’esecuzione di un qualsiasi programma (algoritmo) ha un costo in termini di:
- Complessità Spaziale (utilizzo di memoria)
- Complessità Temporale (tempo di esecuzione)
Queste complessità possono variare all’aumentare al aumentare della dimensione dei dati in input.
Per studiare le complessità di un algoritmo si utilizza il metodo dell’Analisi Asintotica degli Algoritmi.
Notazione asintotica
In matematica la notazione asintotica permette di confrontare il tasso di crescita (comportamento asintotico) di una funzione nei confronti di un’altra.
In informatica il calcolo asintotico è utilizzato per analizzare la complessità di un algoritmo. In particolare modo, per stimare quanto aumenta il tempo di esecuzione al crescere della dimensione dell’input.
Le notazioni asintotiche più comunemente utilizzate sono:
- Notazione Big O (O) è il limite superiore asintotico
- Notazione Omega (Ω) è il limite inferiore asintotico
- Notazione Theta (Θ) è il limite asintotico stretto
Utilizzando la notazione asintotica, possiamo confrontare diversi algoritmi e scegliere quello più efficiente per un dato problema.
Grafico della complessità algoritmica
oss
Nota che le funzioni che ci interessano catturano tempi di esecuzione degli algoritmi e sono quindi sono non negative, pertanto il vincolo dell’asintoticità non negativa non ci fa perdere di generalità.
Teoremi
- Regole sulle costanti moltiplicative
- Regole sulla combattività con la somma
- Regole sulla combattività com il prodotto
Altre osservazioni utili:
Regole sulle costanti moltiplicative
Informalmente
Le costanti moltiplicative si possono ignorare
Regole sulla combattività con la somma
Informalmente
Le notazioni asintotiche commutano con l’operazione somma.
Regole sulla combattività com il prodotto
Informalmente
Le notazioni asintotiche commutano con l’operazione prodotto.