“Big O” notation: che significa? Cosa rappresenta “O grande”? C’è una spiegazione semplice a questa definizione? In questo articolo la approfondiamo per capirne ogni suo dettaglio.
Questo nome, questo “Big O” lo si trova spesso nei titoli accademici quando si studiano gli algoritmi, ma in particolar modo: la loro complessità. Ma prima di spiegare tutto questo, permettimi di presentarmi
Ciao mi chiamo Lorenzo Neri e sono un informatico: realizzo contenuti per aiutare le persone a padroneggiare l’arte del nuovo millennio, ovvero l’informatica!
“Big O” notation: che significa? Cosa rappresenta “O grande”?
Se ti stai chiedendo Cosa rappresenta “O grande” o in inglese “Big O” notation beh… C’è una definizione un po’ tecnichese, ma è la più semplice di tutte:
Big O è una notazione relativa alla rappresentazione di complessità di un algoritmo
Insomma, non suona molto lineare se stai cercando di capire cosa significa e cosa rappresenta “O grande”: dunque vediamo di capire il reale significato dietro tutto questo. Come? Andando ad analizzare parola per parola.
- Relativa: quante volte ci hanno ripetuto il detto “Stai sommando mele con banane”? Il significato di relativo è riferito alla comparazione tra algoritmi. Per intenderci: non puoi comparare un algoritmo che esegue moltiplicazioni tra interi ad uno che ordina una lista di interi. Tuttavia, un algoritmo che esegue la moltiplicazione e uno che esegue l’addizione può darti informazioni significative.
- Rappresentazione: Bene, ok, abbiamo capito bene o male che questa notazione “Big O” serve ad eseguire comparazioni tra algoritmi. Quando si fa un paragone di solito si possono utilizzare non poche metriche. Con Big O riduciamo il numero di metriche ad una sola, ovvero Big O stessa.
Questa variabile è scelta in base ad osservazioni oppure assunzioni. Per esempio, gli algoritmi di ordinamento vengono confrontati di solito tramite le operazioni di comparazione (ovvero, comparando due elementi all’interno di un array, possiamo capire quale sia il loro effettivo ordine). - Complessità: se ci metto un secondo ad ordinare 10000 elementi, quanti ce ne metterò per ordinare un milione di elementi? La complessità in questo caso è una metrica relativa per misurare l’efficienza.
Ora, andiamo oltre, facendo degli esempi veri e propri per approfondire il significato di Big O.
Operazioni aritmetiche dietro “Big O” notation: quali sono?
L’esempio più basico che si possa fare per capire Big O, sono le operazioni aritmetiche. Prendiamo due numeri interi qualsiasi.
Le operazioni base che possiamo fare su questi due numeri sono addizione, sottrazione, moltiplicazione e divisione.
Ognuna di loro, può essere intesa come operazione oppure come problema. Un metodo per risolvere tale problema, lo denominiamo algoritmo.
L’addizione è la più semplice.
Come ci hanno sempre insegnato alle elementari, incolonniamo i due numeri e cominciamo a sommare le cifre una ad una, ricordandoci di eventuali riporti.
A questo punto, l’addizione abbiamo capito che è la parte più “costosa” del nostro algoritmo.
La ragione è semplice: per sommare due numeri da 6 cifre ciascuno per esempio, dobbiamo sommare 6 cifre tra di loro assieme, più un eventuale settima di riporto.
Se sommiamo due numeri da 100 cifre, dovremo eseguire 100 addizioni, se ne abbiamo due da 10000 cifre, ne dovremo eseguire 10000.
Riesci a intravedere il processo?
La complessità è direttamente proporzionale al numero di cifre che compongono i due numeri.
In questo caso, la definizione “Big O”, la usiamo per definire la complessità lineare, ovvero O(n).
Vediamo un po’ che fare con la moltiplicazione.
Cosa rappresenta davvero la notazione “O grande”?
Torniamo al metodo che ci hanno insegnato a scuola.
Di solito, per la moltiplicazione, prendiamo le cifre del primo numero e le moltiplichiamo ciascuna per ognuna delle cifre del secondo, incolonnando poi i risultati ottenuti che andranno sommati assieme.
Per fartela breve, se abbiamo un numero da 100 cifre, dovremo eseguire 10000 moltiplicazioni e 200 addizioni.
Per due numero da un milione di cifre dovremo eseguire un trilione di moltiplicazioni e due milioni di addizioni.
Riesci a intravederlo anche qui il processo?
Più cresciamo con i numeri, più il numero di operazioni da fare è quadratico.
Quadratico, intendo dire che, prendiamo il numero di cifre che dobbiamo moltiplicare fra loro e il numero di operazioni da eseguire sarà quel numero di cifre elevato alla potenza di due.
In questo caso, siamo di fronte alla definizione di complessità quadratica, usando il vero significato di “Big O”, è O(n^2).
Perciò, concludendo, facendo sempre caso agli esempi che ho riportato, stiamo analizzando gli scenari peggiori.
Magari, fra le due operazioni che abbiamo eseguito prima, un numero ha 10 cifre e il secondo solo 4.
Ma in linea generale, bisogna sempre prendere il caso peggiore per stimare “Big O”.
Arrivati a questo punto immagino tu abbia una maggior chiarezza della “Big O” notation: dunque che significa e cosa rappresenta “O grande” detto in italiano, ma se volessimo dare una conclusione più grafica del tutto, penso che questo estratto da Wikipedia sia molto d’impatto:
