In questo tutorial imparerai cosa sono le notazioni asintotiche. Inoltre, imparerai a conoscere la notazione Big-O, la notazione Theta e la notazione Omega.
L'efficienza di un algoritmo dipende dalla quantità di tempo, archiviazione e altre risorse necessarie per eseguire l'algoritmo. L'efficienza viene misurata con l'aiuto di notazioni asintotiche.
Un algoritmo potrebbe non avere le stesse prestazioni per diversi tipi di input. Con l'aumento della dimensione dell'input, le prestazioni cambieranno.
Lo studio del cambiamento nelle prestazioni dell'algoritmo con il cambiamento nell'ordine della dimensione dell'input è definito come analisi asintotica.
Notazioni asintotiche
Le notazioni asintotiche sono le notazioni matematiche utilizzate per descrivere il tempo di esecuzione di un algoritmo quando l'input tende verso un valore particolare o un valore limite.
Ad esempio: nel Bubble sort, quando l'array di input è già ordinato, il tempo impiegato dall'algoritmo è lineare, ovvero il caso migliore.
Ma, quando l'array di input è in condizione inversa, l'algoritmo impiega il tempo massimo (quadratico) per ordinare gli elementi, ovvero il caso peggiore.
Quando la matrice di input non è né ordinata né in ordine inverso, richiede tempo medio. Queste durate sono indicate utilizzando notazioni asintotiche.
Esistono principalmente tre notazioni asintotiche:
- Notazione Big-O
- Notazione Omega
- Notazione Theta
Notazione O grande (notazione O)
La notazione Big-O rappresenta il limite superiore del tempo di esecuzione di un algoritmo. Pertanto, fornisce la complessità del caso peggiore di un algoritmo.
Big-O fornisce il limite superiore di una funzione
O (g (n)) = (f (n): esistono costanti positive c e n 0 tali che 0 ≦ f (n) ≦ cg (n) per ogni n ≧ n 0 )
L'espressione di cui sopra può essere descritta come una funzione che f(n)appartiene all'insieme O(g(n))se esiste una costante positiva ctale che si trovi tra 0e cg(n), per sufficientemente grande n.
Per qualsiasi valore di n, il tempo di esecuzione di un algoritmo non incrocia il tempo fornito da O(g(n)).
Poiché fornisce il tempo di esecuzione nel caso peggiore di un algoritmo, è ampiamente utilizzato per analizzare un algoritmo poiché siamo sempre interessati allo scenario peggiore.
Notazione Omega (notazione Ω)
La notazione Omega rappresenta il limite inferiore del tempo di esecuzione di un algoritmo. Pertanto, fornisce la migliore complessità del caso di un algoritmo.
Omega fornisce il limite inferiore di una funzione
Ω (g (n)) = (f (n): esistono costanti positive c e n 0 tali che 0 ≦ cg (n) ≦ f (n) per ogni n ≧ n 0 )
L'espressione di cui sopra può essere descritta come una funzione f(n)appartiene all'insieme Ω(g(n))se esiste una costante positiva ctale che si trovi sopra cg(n), per sufficientemente grande n.
Per qualsiasi valore di n, il tempo minimo richiesto dall'algoritmo è dato da Omega Ω(g(n)).
Notazione Theta (notazione Θ)
La notazione theta racchiude la funzione dall'alto e dal basso. Poiché rappresenta il limite superiore e inferiore del tempo di esecuzione di un algoritmo, viene utilizzato per analizzare la complessità del caso medio di un algoritmo.
Theta limita la funzione all'interno di fattori costanti
Per una funzione g(n), Θ(g(n))è dato dalla relazione:
Θ (g (n)) = (f (n): esistono costanti positive c 1 , c 2 en 0 tali che 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) per tutti n ≧ n 0 )
L'espressione sopra può essere descritta come una funzione f(n)appartiene all'insieme Θ(g(n))se esistono costanti positive e tali da poter essere inserita tra e , per n sufficientemente grande.c1c2c1g(n)c2g(n)
Se una funzione si f(n)trova ovunque nel mezzo e per tutti , allora si dice che sia asintoticamente vincolata.c1g(n)c2g(n)n ≧ n0f(n)
