Introduzione alla Big-O Notation
Introduzione alla notazione fondamentale per l'analisi del costo di un algoritmo sotto il punto di vista del tempo e della memoria.
Introduzione
Definiamo buono un codice leggibile e scalabile, ovvero un codice che all'aumentare della complessità non preveda un aumento del numero delle operazioni eseguite dall'elaboratore.
La scalabilità si basa, quindi, sul numero di operazioni eseguite e non sul tempo di esecuzione tenendo conto del fatto che due PC diversi eseguono un determinato compito in tempi diversi anche in base alla loro potenza.
Facciamo un esempio definendo una funzione che accetta una array, lo scorre e stampa il valore di ogni elemento pari.
function showEvenElements(array) {
for (let i = 0; i < array.length; i++) {
if (array[i] % 2 == 0)
console.log(array[i]);
}
}
A questo punto eseguiamo la funzione andando a misurare il tempo di esecuzione necessario per completare l'operazione con un input di 10 elementi.
const myArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const startTime = performance.now();
showEvenElements(myArray);
const endTime = performance.now();
console.log(`Tempo di esecuzione: ${endTime - startTime}ms`);
Tempo di esecuzione: 0.19999980926513672ms
Il tempo di esecuzione di questa funzione sul mio PC è di circa 0.2 millisecondi.
Ripetiamo l'esecuzione passando alla funzione un array di 1000 elementi e successivamente di 10000.
const myArray = Array.from(Array(1000).keys());
const startTime = performance.now();
showEvenElements(myArray);
const endTime = performance.now();
console.log(`Tempo di esecuzione: ${endTime - startTime}ms`);
Tempo di esecuzione: 15ms
const myArray = Array.from(Array(10000).keys());
const startTime = performance.now();
showEvenElements(myArray);
const endTime = performance.now();
console.log(`Tempo di esecuzione: ${endTime - startTime}ms`);
Tempo di esecuzione: 164.20000004768372ms
È chiaro che all'aumentare della grandezza dell'input aumenta anche il tempo di esecuzione.
Abbiamo detto però che la scalabilità non si misura in tempo ma in numero di operazioni (ognuna delle quali richiede necessariamente un certo lasso di tempo) e quindi la domanda da farsi è la seguente: all'aumentare della grandezza dell'input aumenta anche il numero delle operazioni che il computer deve eseguire?
O meglio: quando il nostro input cresce, quanto rallenta il nostro algoritmo?
Per misurare l'efficienza in questi termini possiamo utilizzare la Big-O Notation (time complexity) rappresentata con O().
Vediamo quindi come calcolare questa metrica ed i casi più comuni.
O(n)
Nell'esempio mostrato in precedenza possiamo notare come all'aumentare del numero di elementi aumenti anche quello delle operazioni.
In questo caso di parla di tempo di esecuzione lineare e si rappresenta con la notazione O(n) con n che rappresenta il numero di elementi dell'input.
Array con 1 elemento → O(1)
Array con 100 elementi → O(100)
Array con 10000 elementi → O(10000)
Non conoscendo il numero di elementi definito che avrà l'array a tempo di esecuzione, si indica convenzionalmente con la lettera n.
O(1)
Una funzione che esegue sempre un determinato numero di operazioni, indipendentemente dalla dimensione dell'input, è una funzione con un tempo di esecuzione costante in quanto non viene influenzata dalla dimensione dell'argomento passato.
Questa tipologia di funzioni hanno per convenzione una complessità di O(1) indipendente dal numero di operazioni effettivo.
function showFirstElements(array) {
console.log(array[0]);
}
In questo esempio non importa quanto sia grande l'array ricevuto, può essere di un solo elemento o di un milione ma nonostante questo la funzione accede sempre e solo al primo rendendo il numero di operazioni effettuate costante.
Array con 1 elemento → O(1)
Array con 100 elementi → O(1)
Array con 10000 elementi → O(1)
O(n²)
Quando abbiamo a che fare con cicli annidati basati sullo stesso input allora si ha una crescita del numero delle operazioni esponenziale e questa complessità si rappresenta con la notazione O(n²).
function showAllPairs(array) {
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length; j++) {
console.log(`${array[i]}-${array[j]}`);
}
}
}
Ogni volta che l’input aumenta di una grandezza il numero di operazioni aumenta del doppio (2 numeri = 4 operazioni, 3 numeri = 9 operazioni, 4 numeri = 16 operazioni, …).
Un algoritmo con questa efficienza è decisamente scarso.
Nel caso in cui avessimo due differenti input annidati uno dentro l'altro allora potremmo rappresentare la Big-O come O(n1*n2).
function showAllPairs(array1, array2) {
for (let i = 0; i < array1.length; i++) {
for (let j = 0; j < array2.length; j++) {
console.log(`${array1[i]}-${array2[j]}`);
}
}
}
O(log n)
Alcune strutture dati, come gli alberi binari, non necessitano di iterare ogni nodo per raggiungere quello desiderato ma, nel peggiore dei casi, sarà necessario attraversare un solo nodo per ogni livello della struttura dati.
Come possiamo notare non conta il numero dei nodi di per se ma è più importante il numero di livelli che la struttura presenta.
Questo significa che affinché ci sia un aumento lineare della time complexity è necessario l'aumento esponenziale del numero degli elementi dell'input.
Alla luce di questo la sua Big-O Notation è identificabile come O(log n).
Subito dopo O(1), questa è la metrica più efficiente disponibile.
Calcolo della Big-O
Ogni loop all'interno della funzione ha una time complexity di O(n) mentre ogni istruzione singola ha una complessità di O(1).
function test(array) {
let x = 10; // O(1)
x = 20; // O(1)
for (let i = 0; i < array.length; i++) { // O(n)
x++;
}
return x; // O(1)
}
La Big-O di questa funzione è quindi O(3 + n).
function test(array) {
for (let i = 0; i < array.length; i++) { // O(n)
console.log(array[i]);
}
for (let i = 0; i < array.length; i++) { // O(n)
console.log(array[i]);
}
}
La Big-O di una funzione con due loop sequenziali è O(2n).
function test(array) {
for (let i = 0; i < array.length; i++) { // O(n)
for (let j = 0; j < array.length; j++) { // O(n)
console.log(array[i] + array[j]);
}
}
}
Due loop annidati portano la time complexity a O(n²).
Ove necessario è possibile eseguire delle semplificazioni sul calcolo effettuato seguendo alcune regole.
Regole della Big-O
Considerare il caso peggiore
Prendiamo in considerazione la possibilità di avere una funzione con time complexity di O(n) ed una situazione in cui tale funzione riceva un array di 1000 elementi.
Ora consideriamo che lo scopo di questa funzione sia quello di cercare un determinato elemento all'interno dell'input e restituire la sua posizione alla funzione chiamante.
L'elemento che ci interessa potrebbe essere in prima posizione e quindi necessitare di una sola operazione di ricerca rendendo il processo molto rapido, oppure in ultima posizione e questo comporterebbe la necessità di scorrere l'intera struttura dati.
È bene tenere a mente che questa metrica è del tutto teorica e che si concentra sempre sul caso peggiore, quindi consideriamo sempre il calcolo più pesante possibile.
Rimozione costanti
Nel caso avessimo una Big-O con valori costanti (es. 1, 20 o 100) e con qualsiasi forma di n (dimezzato, moltiplicato, sottratto, ...) bisogna tenere a mente che quest'ultimo potrebbe essere talmente grande da rendere il valore costante insignificante e di conseguenza la Big-O si semplifica sempre in O(n) facendo decadere ogni valore costante utilizzato.
Questo avviene perché questa metrica ci deve far capire solamente se stiamo lavorando con funzioni lineari, costanti, esponenziali, logaritmiche, ..., e quindi se l'algoritmo pensato è scalabile o meno.
O(3 + n) → O(n)
O(2n) → O(n)
O(n + 5000000000000) → O(n)
O(n/2) → O(n)
Se invece avessimo una time complexity costante potremmo semplificarla sempre in O(1).
O(1000000000) → O(1)
O(100) → O(1)
Input molteplici
Se una funzione accetta due differenti array ed al suo interno cicla prima uno e poi l'altro allora è necessario fare una precisazione: essendo due loop che lavorano su due array separati, la Big-O sarà composta da entrambi e quindi varrà O(n1 + n2).
function test(array1, array2) {
for (let i = 0; i < array1.length; i++) { // O(array1)
console.log(array1[i]);
}
for (let i = 0; i < array2.length; i++) { // O(array2)
console.log(array2[i]);
}
}
Le complessità si sommano per cicli consecutivi e si moltiplicano per cicli annidati.
Termine principale
Per il calcolo dell'efficienza è necessario dare sempre la priorità al termine principale e con un peso maggiore.
function test(array) {
for (let i = 0; i < array.length; i++) {
console.log(array[i]);
}
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length; j++) {
console.log(array[i]);
}
}
}
La time complexity di questa funzione è O(n + n²) che si semplifica in O(n²) essendo quest'ultimo il termine principale di maggior peso.
Space Complexity
Oltre ad utilizzare la Big-O per la misura dell'efficienza è possibile utilizzarla anche per effettuare il calcolo della space complexity, ovvero la metrica di utilizzo della memoria addizionale dedicata alla funzione.
function test(array) {
for (let i = 0; i < array.length; i++) {
console.log("Ciao");
}
}
In questa funzione stiamo allocando la memoria solo per il contatore del for quindi la space complexity è O(1).
function test(oldArray) {
let array = [];
for (let i = 0; i < oldArray.length; i++) {
array[i] = oldArray[i];
}
}
Nell'ultimo esempio, invece, avvengo n allocazioni, in base alla grandezza dell'input, quindi ritroviamo una complessità di O(n).
Conclusione
Possiamo quindi dire che la Big-O Notation è una metrica per verificare l'efficienza (sia nel numero delle operazioni che nella memoria utilizzata) di un algoritmo.
È buona pratica calcolarla ed eventualmente ridurre la complessità dei nostri algoritmi per renderli più efficienti e scalabili possibile.
👋