Complessità computazionale

La complessità computazionale è lo studio di quanto tempo e quanta memoria un algoritmo richiede in base alla dimensione dell’input. Ci aiuta a confrontare algoritmi e scegliere quello più efficiente.

Notazione Big-O

La notazione Big-O descrive il peggior caso di un algoritmo, ossia il tempo massimo che può impiegare in funzione dell’input. Alcune delle complessità più comuni sono:

Notazione	Nome	Esempio
O(1)	Tempo costante	Accesso a un elemento in un array
O(log n)	Logaritmico	Ricerca binaria
O(n)	Lineare	Scansione di un array
O(n log n)	Quasi-lineare	Merge Sort, Quick Sort nel caso medio
O(n²)	Quadratico	Bubble Sort, Selection Sort
O(2ⁿ)	Esponenziale	Problemi di backtracking (es. Torre di Hanoi)
O(n!)	Fattoriale	Permutazioni di una lista

Perché la Complessità è Importante?

• Aiuta a scegliere l’algoritmo più veloce ed efficiente.
• Evita problemi di prestazioni su dati di grandi dimensioni.
• È fondamentale in campi come l’intelligenza artificiale e la cyber-security.