Complessità computazionale
La complessità computazionale riguarda essenzialmente due aspetti:
- Lo spazio occupato dall’algoritmo
- Il tempo di esecuzione
Ci sono vari ordini di complessità computazionale degli algoritmi.
Il grafico sottostante ne riassume i principali.
La complessità computazione di un ciclo for, while o do-while è data dal prodotto della complessità del corpo del ciclo stesso (O(f(n)) per il numero di volte che esso viene eseguito ( O(k)). Nel caso del ciclo for la complessità delle operazioni di inizializzazione, confronto ed incremento è pari ad O(1) quindi trascurabile. In definitiva, il tempo di esecuzione è pari a:
O(k * f(n))
ELIMINARE GLI ELEMENTI COSTANTI
È opportuno rimuovere i valori costanti dal tempo di esecuzione. Ad esempio, un algoritmo che potrebbe essere descritto con una complessità computazionale pari a O(2N), viene indicato come O(N). Si consideri un semplice algoritmo di ricerca dei valori minimo e massimo in un array.
int min = array[0];
int max = array[0];
for (int i=1; i<array.length; i++) {
if (array[i] < min)
min = array[i];
if (array[i] > max)
max = array[i];
}
int min = array[0];
int max = array[0];
for (int i=1; i<array.length; i++) {
if (array[i] < min)
min = array[i];
}
for (int j=1; j<array.length; j++) {
if (array[j] > max)
max = array[j];
}
Il tempo di esecuzione di ambedue gli algoritmi è O(N). Nel secondo esempio vengono utilizzati due cicli for anziché uno, ma è errato indicare il tempo di esecuzione come O(2N), perché andrebbe fatta un’analisi a basso livello di come il compilatore effettuerà le varie ottimizzazioni e tutta un’altra serie di dettagli per comprenderne il reale tempo di esecuzione. La Big O ci permette di eliminare le costanti e di darci un’idea di come il tempo di esecuzione scali.
ELIMINARE I TERMINI NON DOMINANTI
Così come per i valori costanti, bisogna eliminare i termini non dominanti, poiché non sono particolarmente importanti ai fini dell’analisi Big O. Ad esempio:
- O(N²+N) diventa O(N²);
- O(N²+N²) diventa O(N²);
- O(N²+N) diventa O(N²);
- O(N + log N) diventa O(N);
IF
Ha complessità computazionale O(1).
CHIAMATE A FUNZIONI
La complessità computazionale di una chiamata di funzione è data dalla somma del costo di esecuzione della funzione stessa (O(f(n)) ed il costo della chiamata
WHILE E FOR
for (int i=0; i<arrA.length; i++) {
for (int j=0; j<arrB.length; j++) {
print(arrA[i] + " - " + arrB[j]);
}
}
Quando ci si trova davanti a due cicli for si fa confusione sul quando moltiplicare i due tempi di esecuzione e sul quando sommarli. Se i due cicli for sono annidati, bisognerà moltiplicare i tempi di esecuzione.
Il tempo di esecuzione del precedente esempio è pari a O(A*B).
Diversamente, se i due cicli for sono sequenziali, bisognerà sommare i tempi di esecuzione:
for (int i=0; i<arrA.length; i++) {
print(arrA[i]);
}
for (int j=0; j<arrB.length; j++) {
print(arrB[j]);
}
Il tempo di esecuzione del precedente esempio è pari a O(A+B).
LOG N
Spesso si notano valori di O(log N) nei tempi di esecuzione degli algoritmi. Per identificare semplicemente quest’ordine di funzione bisogna notare se il problema ha un numero di elementi che viene dimezzato ogni volta; in tal caso, molto probabilmente, ci troveremo di fronte ad un tempo di esecuzione pari a O(log N).
Un esempio si ha nell’algoritmo di ricerca binaria: ad ogni iterazione dimezziamo il numero di elementi dell’array da esaminare