Che cos'è la notazione Big-O?
Cominciamo con un semplice esempio. Immaginate di voler trasferire una certa quantità di dati ad un vostro amico negli stai uniti. La situazione è molto urgenti quindi volete assicurarvi che il trasferimento dei dati accada nel modo più veloce possibile. La maggior parte delle persone vi proporranno come soluzione uno dei vari tipi di trasferimento dati elettronico come: email o FTP. Questa soluzione purtroppo è solo parzialmente corretta dato che non è sempre la soluzione più efficace. Se il file da trasferire è di piccole dimensioni, ovviamente il metodo più veloce è inviare un'email o FTP, ma se vogliamo trasferire 1 Terabyte di dati? Trasferire questa grande quantità di dati attraverso la rete internet potrebbe facilmente impiegare più di una giornata anche con una buona connessione in Fibra. E se i dati pesano 10 Terabyte? La situazione comincia a diventare impossibile. In alcuni casi, la soluzione più veloce è prendere il primo volo per gli stati uniti e trasferire manualmente i dati al vostro amico. Questo processo impiegherebbe all'incirca dalle 10-15 ore dipendendo dove il vostro amico vive. Se le dimensioni del file solo incredibilmente grandi la soluzione più veloce potrebbe essere anche la nave.
Questo esempio è utile perché ci permette di capire come un certo processo o algoritmo cambia in proporzione all'input dato. Nell'esempio abbiamo due diversi "algoritmi" o processi.
- Trasferimento elettronico: O(n) - Il tempo impiegato per trasferire il file è aumenta in modo lineare rispetto alle dimensioni del file. In questo caso possiamo considerare n come il numero di file da trasferire. Il simbolo O(n) ci dice il tempo di esecuzione di questo processo aumenta in modo linearmente proporzionale al numero dei file.
- Trasporto fisco (aereo): O(1) - Se scegliamo l'opzione di traferire i file in persona con un aereo o nave, il tempo di esecuzione del processo non dipende più dalla dimensione del file da trasferire, ma dalla durata del volo. Possiamo assumere che la durata del volo sia costante, quindi possiamo dire che anche il tempo di esecuzione dell'algoritmo sia costante. Questo viene rappresentato con il simbolo O(1).
Non importa quanto grande sia la costante, un algoritmo che cresce in modo lineare rispetto all'input prima o poi dovrà sorpassare l'algoritmo costante.
Si può inserire qualsiasi funzione matematica all'interno delle parentesi della O-Grande, ma alcuni dei runtime che vediamo negli algoritmi più comuni includono: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n)...
Più la funzione nelle parentesi cresce velocemente più l'algoritmo impiega per terminare quando l'input aumenta. Per esempio un algoritmo di tipo O(n) sarà molto più veloce dell'algoritmo O(n^2) per input molto grandi. Per input di piccole dimensioni la differenza non sarà molto notevole. Questo è dato dal fatto che il grafico della funzione f(x)=x e f(x)=x^2 sono simili per piccoli valori di x, ma la seconda funzione cresce molto più velocemente quando x aumenta.
Differenza tra Big O, Big Theta e Big Omega
Il termine Big O o O Grande viene usato per specificare il limite superiore sul tempo di esecuzione. Un algoritmo di tipo O(n) come il trasferimento elettronico di dati può essere caratterizzato anche come un algoritmo O(n^2) dato che il limite superiore è comunque valido. Per esempio se il peso x di una persona è 60kg è corretto dire x < 60 ma è anche corretto dire x < 1000. Lo stesso vale per la notazione O-Grande.FOTO grafico
Come calcolare la Complessità temporale di un algoritmo
È perfettamente possibile per un algoritmo di tipo O(n) di impiegare più tempo di un algoritmo O(1) per alcuni casi. Come abbiamo visto nell'esempio del trasferimento di dati: per grandi valori di n è meglio prendere l'aereo (O(1)) che inviare n dati per email (O(n)). Questo concetto è importante da capire perché spesso la notazione O-Grande viene usato nel modo sbagliato. Molti credono che questa la velocità dell'algoritmo, ma questo non è corretto. La notazione Big O indica il "tasso di crescita" dell'algoritmo rispetto all'input. Per questo quando si parla di un algoritmo O(2n) o O(3n) in realtà si sta semplicemente parlando di un algoritmo O(n). Questo è dato dal fatto che entrambi gli algoritmi scalano linearmente.
Consideriamo i due algoritmi in basso.
// Algoritmo 1
int n = 100;
for(int i = 0 ; i < n ; i++){
System.out.println("Ciao Devnews!");
}// Algoritmo 2
int n = 100;
for(int i = 0 ; i < n ; i++){
System.out.println("Ciao Devnews!");
}
for(int i = 0 ; i < n ; i++){
nbsp; System.out.println("Ciao ancora Devnews!");
}
Ovviamente se eseguiamo i due algoritmi per lo stesso valore di n, l'algoritmo 1 impiegherà meno tempo rispetto all'algoritmo 2 per completare. Questo non significa che in termini di Big O i due algoritmi siano diversi. Molti penserebbero di usare la notazione O(n) per il primo algoritmo (dato che esegue n iterazioni) e O(2n) per il secondo algoritmo (dato che esegue le n iterazioni due volte). Come abbiamo detto precedentemente, il tasso di crescita dei due algoritmi rispetto ad n è uguale. Se ancora non vi è chiaro potete immaginare le due rette che si ottengono tracciando le rette y=x e y=2x. Anche se la seconda retta ha un inclinazione maggiore questa è comunque una retta. Questo significa il tempo di esecuzione aumenta in modo lineare. In altre parole, il tempo di esecuzione aumenta di un valore costante per ogni unita di n. Questo è vero sia per l'algoritmo 1 e 2 quindi possiamo dire che i due algoritmi entrambi crescono linearmente e non vi è alcuna differenza in termini di tasso di crescita.
int n = 100;
for(int i = 0 ; i < n ; i++){
System.out.println("Ciao Devnews");
}
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++){
System.out.println("Ciao Ancora Devnews");
}
}
A primo istinto verrebbe da dire che questo algoritmo è di tipo O(n + n^2) dato che prima esegue n iterazioni e poi n^2 iterazioni. Come prima abbiamo omesso la costante perché non necessaria per caratterizzare il tasso di crescita, anche qui possiamo fare lo stesso con n. La runtime di questo algoritmo è semplicemente O(n^2). Perché? con l'aumentare di n il doppio for loop causerà un aumento quadratico nel tempo di esecuzione. Per esempio se n è 10, vengono eseguite 100 iterazioni. Se n=20 -> 400 iterazioni, n=30 -> 900...
Se consideriamo anche il termine lineare n, rispetto al termine quadratico non influenza il tasso di crescita. Per esempio se n=10 -> 110 iterazioni (n+n^2), n=20->420 iterazioni, n=30 -> 930 iterazioni. Vedete che il termine lineare del primo for loop non ha influenza sull'andamento della crescita del numero di iterazioni?
Vediamo un esempio:
Domanda: Qual'è la vera complessità temporale di un algoritmo O(n^2 + n)?
Risposta: O(n^2)
Spiegazione: Il polinomio n^2 cresce in maniera più veloce rispetto a n (come mostrato in foto) quindi il polinomio n viene dominato dal polinomio n^2
Domanda: Qual'è la vera complessità temporale di un algoritmo O(2log(n) + n)?
Risposta: O(n)
| Funzione | Notazione Big O |
| For loop for(int i = 0 ; i < n ; i++){...} | O(n) |
| Doppio for loop for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){...} } | O(n^2) |
| x loop nidificati | O(n^x) |
| Ricorsivamente dividere n elementi a metà Fino ad ottenere un solo elemento. Per esempio Binary search se n=8, -> 4, 2, 1 | O(log(2,n)) Logaritmo in base due di n |
| Inserire binary search in un for loop | O(n*log(2,n)) |
Moltiplicare o addizionare i tempi di esecuzione?
Immaginiamo di avere un algoritmo composto da due passi. Come sapere se i tempi di esecuzioni dei due passi vanno addizionato o moltiplicati?
Prendiamo in considerazioni due algoritmi:
// Algoritmo 1 for(int i = 0 ; i < A ; i++){ // passo 1 } for(int j = 0 ; j < B ; j++){// passo 2 }
// Algoritmo 2 for(int i = 0 ; i < A ; i++){// passo 1for(int j = 0 ; j < B ; j++){// passo 2} }
Nel secondo algoritmo invece vengono eseguite A operazioni 1 e per ogni operazione 1 vengono eseguite altre B operazione 2. In totale le operazioni eseguite dall'algoritmo sono nell'ordine O(A*B).