Che cosa si intende per complessità di un algoritmo?

La complessità descrive come crescono le risorse richieste da un algoritmo al crescere della dimensione dell’input, soprattutto tempo e spazio. In pratica non interessa il tempo preciso su una macchina specifica, ma l’andamento asintotico. Serve per confrontare algoritmi in modo indipendente dall’implementazione.

Che cosa indica la notazione O grande?

La notazione O grande fornisce un limite asintotico superiore della crescita di una funzione. Dire che un algoritmo è O(f(n)) significa che, per n sufficientemente grande, il suo costo non cresce più velocemente di f(n) a fattori costanti vicino. È la notazione più usata per esprimere il caso peggiore.

Che differenza c’è tra O grande, Omega e Theta?

O grande descrive un limite superiore asintotico, Omega un limite inferiore asintotico, Theta un limite stretto, cioè superiore e inferiore insieme. Se un algoritmo è Theta(f(n)), allora la sua crescita è dell’ordine di f(n) in modo preciso asintoticamente. Queste notazioni servono a caratterizzare il comportamento dell’algoritmo senza dipendere da costanti.

Perché nell’analisi asintotica si trascurano costanti e termini minori?

Perché quando l’input cresce molto, le costanti moltiplicative e i termini di grado più basso incidono poco rispetto al termine dominante. L’analisi asintotica mira a descrivere la classe di crescita, non la misura esatta su input piccoli. Così si possono confrontare algoritmi in modo robusto.

Come si definiscono caso migliore, medio e peggiore di un algoritmo?

Il caso migliore è l’input che porta al costo minimo, il caso peggiore quello che porta al costo massimo, mentre il caso medio è il costo atteso su tutti gli input secondo una distribuzione scelta. Sono tre analisi diverse e possono dare risultati molto differenti. Un algoritmo va quindi studiato non solo nel peggiore, ma anche nel comportamento medio quando serve.

Qual è la complessità della ricerca lineare?

La ricerca lineare scandisce gli elementi uno alla volta finché trova l’elemento cercato o termina la sequenza. Ha complessità lineare nel caso medio e nel caso peggiore, mentre nel caso migliore è costante se il primo elemento è quello cercato. È semplice e non richiede dati ordinati.

Qual è la complessità della ricerca binaria e quali sono le sue condizioni d’uso?

La ricerca binaria divide ripetutamente a metà l’intervallo di ricerca, quindi ha complessità logaritmica nel caso medio e nel caso peggiore. Funziona però solo su dati ordinati e con accesso diretto agli elementi, come in un array. Il caso migliore è costante se l’elemento cercato è al centro al primo confronto.

Come funziona bubble sort e qual è la sua complessità?

Bubble sort confronta elementi adiacenti e li scambia se sono nell’ordine sbagliato, ripetendo più passate finché l’array è ordinato. Nel caso medio e peggiore è quadratico, mentre con un controllo di arresto anticipato il caso migliore può diventare lineare se l’array è già ordinato. È un algoritmo semplice ma poco efficiente su input grandi.

Come funziona insertion sort e perché può essere conveniente su input quasi ordinati?

Insertion sort costruisce progressivamente una parte ordinata inserendo ogni nuovo elemento nella posizione corretta. Nel caso medio e peggiore è quadratico, ma nel caso migliore è lineare quando l’array è già ordinato o quasi ordinato. È spesso utile su input piccoli o con alta località d’ordine.

Qual è l’idea di merge sort e quale complessità ha?

Merge sort usa la strategia divide et impera: divide l’array in due metà, ordina ricorsivamente le metà e poi le fonde in tempo lineare. La sua complessità è Theta(n log n) in tutti i casi principali, perché la divisione continua su livelli logaritmici e la fusione costa lineare per livello. Richiede però spazio aggiuntivo per la fusione.

Qual è l’idea di quicksort e perché il suo caso peggiore è diverso dal caso medio?

Quicksort sceglie un pivot, partiziona gli elementi rispetto al pivot e ordina ricorsivamente le due parti. In media ha complessità Theta(n log n), perché il partizionamento tende a bilanciare le chiamate ricorsive; nel caso peggiore, invece, il pivot produce partizioni molto sbilanciate e il costo degrada a Theta(n^2). È spesso molto veloce in pratica, ma il suo comportamento dipende dalla scelta del pivot.

Confronta gli algoritmi di ordinamento studiati in termini di efficienza e spazio.

Bubble sort e insertion sort sono semplici ma quadratici nel caso medio e peggiore, quindi non sono adatti a grandi quantità di dati. Merge sort garantisce Theta(n log n) ma richiede spazio aggiuntivo, mentre quicksort ha in media Theta(n log n) ed è spesso in-place, ma può degradare nel peggiore a quadratico. La scelta dipende quindi dal compromesso tra prestazioni, spazio e prevedibilità.

Da dove conviene partire nello studio?

Parti da O grande, Omega e Theta, poi collega subito queste notazioni a ricerca lineare, ricerca binaria e ai quattro ordinamenti principali.

Se ho poco tempo, cosa devo ripassare per primo?

Ripassa le complessità di ricerca lineare e binaria, poi bubble sort, insertion sort, merge sort e quicksort con i rispettivi casi migliore, medio e peggiore.

Come posso collegare bene questo argomento agli altri?

Collega la complessità alle strutture dati e alle ricorrenze, perché lì si vede davvero perché un algoritmo scala meglio di un altro.

Guida aggiornata: settembre 2026 · a cura di Skooly · tutte le guide · altre domande di programmazione

Domande d'esame sulla complessità degli algoritmi: le 12 che escono davvero, con le risposte

Su questo argomento il docente di solito vuole vedere se sai distinguere bene tra complessità asintotica, caso migliore/medio/peggiore e se sai applicare queste idee ad algoritmi concreti. Ti può chiedere non solo di definire le notazioni, ma anche di confrontare ricerca e ordinamenti, spiegando perché un algoritmo è più efficiente di un altro.

In due minuti: La complessità di un algoritmo misura come crescono il tempo di esecuzione e lo spazio usato al crescere della dimensione dell’input. Per descriverla si usano le notazioni asintotiche, soprattutto O grande, Omega e Theta, che trascurano costanti e termini meno significativi. Per la ricerca, la scansione lineare è lineare, mentre la ricerca binaria è logaritmica ma richiede una struttura ordinata. Per gli ordinamenti, bubble e insertion sono quadratici nel caso medio e peggiore, merge sort è sempre n log n ma usa spazio aggiuntivo, quicksort è molto efficiente in media ma può degradare a quadratico nel peggiore.

I termini che il prof si aspetta: complessità temporale · complessità spaziale · notazione O grande · notazione Omega · notazione Theta · caso migliore · caso medio · caso peggiore · ricerca lineare · ricerca binaria · merge sort · quicksort.

Le domande che escono all'esame

Che cosa si intende per complessità di un algoritmo?

La complessità descrive come crescono le risorse richieste da un algoritmo al crescere della dimensione dell’input, soprattutto tempo e spazio. In pratica non interessa il tempo preciso su una macchina specifica, ma l’andamento asintotico. Serve per confrontare algoritmi in modo indipendente dall’implementazione.

Cosa vuole sentire: Vuole una definizione generale ma rigorosa, con l’idea di crescita rispetto alla dimensione dell’input. Errore tipico: Confondere la complessità con il tempo misurato in secondi su un computer reale.
Che cosa indica la notazione O grande?

La notazione O grande fornisce un limite asintotico superiore della crescita di una funzione. Dire che un algoritmo è O(f(n)) significa che, per n sufficientemente grande, il suo costo non cresce più velocemente di f(n) a fattori costanti vicino. È la notazione più usata per esprimere il caso peggiore.

Cosa vuole sentire: Vuole il significato di limite superiore asintotico e l’uso corretto nel confronto tra algoritmi. Errore tipico: Dire che O grande è una stima esatta o il valore preciso del tempo di esecuzione.
Che differenza c’è tra O grande, Omega e Theta?

O grande descrive un limite superiore asintotico, Omega un limite inferiore asintotico, Theta un limite stretto, cioè superiore e inferiore insieme. Se un algoritmo è Theta(f(n)), allora la sua crescita è dell’ordine di f(n) in modo preciso asintoticamente. Queste notazioni servono a caratterizzare il comportamento dell’algoritmo senza dipendere da costanti.

Cosa vuole sentire: Vuole il confronto formale tra le tre notazioni e il significato di Theta. Errore tipico: Scambiare Omega con O o usare Theta come se fosse un generico sinonimo di O.
Perché nell’analisi asintotica si trascurano costanti e termini minori?

Perché quando l’input cresce molto, le costanti moltiplicative e i termini di grado più basso incidono poco rispetto al termine dominante. L’analisi asintotica mira a descrivere la classe di crescita, non la misura esatta su input piccoli. Così si possono confrontare algoritmi in modo robusto.

Cosa vuole sentire: Vuole la motivazione teorica del perché l’asintotica è utile. Errore tipico: Pensare che ignorare le costanti significhi perdere informazione rilevante in assoluto.
Come si definiscono caso migliore, medio e peggiore di un algoritmo?

Il caso migliore è l’input che porta al costo minimo, il caso peggiore quello che porta al costo massimo, mentre il caso medio è il costo atteso su tutti gli input secondo una distribuzione scelta. Sono tre analisi diverse e possono dare risultati molto differenti. Un algoritmo va quindi studiato non solo nel peggiore, ma anche nel comportamento medio quando serve.

Cosa vuole sentire: Vuole la distinzione rigorosa tra i tre casi, soprattutto il significato di caso medio. Errore tipico: Dire che il caso medio è semplicemente la media aritmetica dei casi possibili senza specificare la distribuzione.
Qual è la complessità della ricerca lineare?

La ricerca lineare scandisce gli elementi uno alla volta finché trova l’elemento cercato o termina la sequenza. Ha complessità lineare nel caso medio e nel caso peggiore, mentre nel caso migliore è costante se il primo elemento è quello cercato. È semplice e non richiede dati ordinati.

Cosa vuole sentire: Vuole la complessità nei tre casi e il fatto che non richiede ordinamento. Errore tipico: Dimenticare che il caso migliore è O(1) oppure confondere il comportamento medio con quello migliore.
Qual è la complessità della ricerca binaria e quali sono le sue condizioni d’uso?

La ricerca binaria divide ripetutamente a metà l’intervallo di ricerca, quindi ha complessità logaritmica nel caso medio e nel caso peggiore. Funziona però solo su dati ordinati e con accesso diretto agli elementi, come in un array. Il caso migliore è costante se l’elemento cercato è al centro al primo confronto.

Cosa vuole sentire: Vuole la logica del dimezzamento e il vincolo fondamentale dell’ordinamento. Errore tipico: Dire che basta qualunque struttura dati o dimenticare che senza ordinamento la ricerca binaria non è applicabile.
Come funziona bubble sort e qual è la sua complessità?

Bubble sort confronta elementi adiacenti e li scambia se sono nell’ordine sbagliato, ripetendo più passate finché l’array è ordinato. Nel caso medio e peggiore è quadratico, mentre con un controllo di arresto anticipato il caso migliore può diventare lineare se l’array è già ordinato. È un algoritmo semplice ma poco efficiente su input grandi.

Cosa vuole sentire: Vuole il meccanismo a scambi adiacenti e la complessità nei diversi casi. Errore tipico: Descriverlo in modo troppo generico o dimenticare l’ottimizzazione del caso migliore.
Come funziona insertion sort e perché può essere conveniente su input quasi ordinati?

Insertion sort costruisce progressivamente una parte ordinata inserendo ogni nuovo elemento nella posizione corretta. Nel caso medio e peggiore è quadratico, ma nel caso migliore è lineare quando l’array è già ordinato o quasi ordinato. È spesso utile su input piccoli o con alta località d’ordine.

Cosa vuole sentire: Vuole la strategia di inserimento e il motivo della buona prestazione su dati quasi ordinati. Errore tipico: Confonderlo con bubble sort o non cogliere la dipendenza dalla quantità di disordine.
Qual è l’idea di merge sort e quale complessità ha?

Merge sort usa la strategia divide et impera: divide l’array in due metà, ordina ricorsivamente le metà e poi le fonde in tempo lineare. La sua complessità è Theta(n log n) in tutti i casi principali, perché la divisione continua su livelli logaritmici e la fusione costa lineare per livello. Richiede però spazio aggiuntivo per la fusione.

Cosa vuole sentire: Vuole il legame tra divide et impera, fusione e complessità n log n. Errore tipico: Dimenticare che il costo della fusione è lineare o non citare lo spazio extra.
Qual è l’idea di quicksort e perché il suo caso peggiore è diverso dal caso medio?

Quicksort sceglie un pivot, partiziona gli elementi rispetto al pivot e ordina ricorsivamente le due parti. In media ha complessità Theta(n log n), perché il partizionamento tende a bilanciare le chiamate ricorsive; nel caso peggiore, invece, il pivot produce partizioni molto sbilanciate e il costo degrada a Theta(n^2). È spesso molto veloce in pratica, ma il suo comportamento dipende dalla scelta del pivot.

Cosa vuole sentire: Vuole la relazione tra partizionamento, bilanciamento e differenza tra medio e peggiore. Errore tipico: Dire solo che quicksort è veloce senza spiegare quando e perché può peggiorare.
Confronta gli algoritmi di ordinamento studiati in termini di efficienza e spazio.

Bubble sort e insertion sort sono semplici ma quadratici nel caso medio e peggiore, quindi non sono adatti a grandi quantità di dati. Merge sort garantisce Theta(n log n) ma richiede spazio aggiuntivo, mentre quicksort ha in media Theta(n log n) ed è spesso in-place, ma può degradare nel peggiore a quadratico. La scelta dipende quindi dal compromesso tra prestazioni, spazio e prevedibilità.

Cosa vuole sentire: Vuole un confronto ragionato e non solo la lista delle complessità. Errore tipico: Memorizzare le formule senza saper dire quale algoritmo è preferibile in quale situazione.

Fatti interrogare sulla complessità degli algoritmi, come all'esame. Carica le tue dispense, le slide o le sbobine, scegli il livello università e Skoo ti fa queste domande a voce, con il rigore di un esame: ti incalza se sei vago e alla fine ti dà una pagella sui quattro criteri, con le frasi che hai detto. I primi 30 minuti sono gratis, senza carta. Simula l'esame sulla complessità degli algoritmi

Le risposte vaghe che non passano

«È la misura di quanto un algoritmo è veloce.»: Meglio: È la misura asintotica di come crescono tempo e spazio richiesti da un algoritmo al crescere della dimensione dell’input.
«La complessità O grande vuol dire che l’algoritmo impiega esattamente quel tempo.»: Meglio: La notazione O grande dà un limite superiore asintotico, non un tempo esatto.
«La ricerca binaria è sempre migliore della lineare.»: Meglio: La ricerca binaria è più efficiente solo su dati ordinati e con accesso diretto; su dati non ordinati non è applicabile.

I collegamenti che fanno salire il voto

Analisi degli algoritmi — ricorrenze e divide et impera. Ti aiuta a giustificare formalmente la complessità di merge sort e quicksort.
Strutture dati — array, liste e accesso casuale. Serve per capire perché la ricerca binaria richiede accesso diretto e perché certe operazioni costano di più su alcune strutture.
Basi di dati — indici e ordinamento dei dati. Collega la complessità della ricerca e dell’ordinamento alla progettazione di accessi efficienti sui dati persistenti.

Come ti valuta la pagella sulla complessità degli algoritmi

Un'interrogazione si valuta su quattro criteri. Ecco cosa fa la differenza in questo argomento:

Criterio	Cosa fa la differenza qui
Conoscenza dei contenuti	Fa la differenza saper definire bene O, Omega e Theta e associare a ogni algoritmo i casi migliore, medio e peggiore corretti.
Correttezza espositiva e lessico specifico	Premia chi distingue chiaramente il meccanismo dell’algoritmo dalla sua complessità e usa il lessico tecnico in modo preciso.
Capacità di analisi e collegamenti	Conta molto saper spiegare perché merge sort è n log n e perché quicksort può degradare, non solo ricordare la formula.
Autonomia nell'argomentare	Il voto sale se sai confrontare gli algoritmi e scegliere quello adatto in base a input ordinato, spazio disponibile e prevedibilità.

Criterio

Cosa fa la differenza qui

Conoscenza dei contenuti

Fa la differenza saper definire bene O, Omega e Theta e associare a ogni algoritmo i casi migliore, medio e peggiore corretti.

Correttezza espositiva e lessico specifico

Premia chi distingue chiaramente il meccanismo dell’algoritmo dalla sua complessità e usa il lessico tecnico in modo preciso.

Capacità di analisi e collegamenti

Conta molto saper spiegare perché merge sort è n log n e perché quicksort può degradare, non solo ricordare la formula.

Autonomia nell'argomentare

Il voto sale se sai confrontare gli algoritmi e scegliere quello adatto in base a input ordinato, spazio disponibile e prevedibilità.

Domande frequenti

Da dove conviene partire nello studio?: Parti da O grande, Omega e Theta, poi collega subito queste notazioni a ricerca lineare, ricerca binaria e ai quattro ordinamenti principali.
Se ho poco tempo, cosa devo ripassare per primo?: Ripassa le complessità di ricerca lineare e binaria, poi bubble sort, insertion sort, merge sort e quicksort con i rispettivi casi migliore, medio e peggiore.
Come posso collegare bene questo argomento agli altri?: Collega la complessità alle strutture dati e alle ricorrenze, perché lì si vede davvero perché un algoritmo scala meglio di un altro.

Altre domande d'esame di programmazione

La programmazione a oggetti · La ricorsione · Le basi di dati e SQL · Le strutture dati · Variabili, tipi e controllo del flusso · tutti gli argomenti di programmazione

Come si prepara un orale universitario: simulare l'esame orale · Skooly per l'università.

Le domande e le risposte modello di questa pagina sono generate con l'intelligenza artificiale a partire dal programma scolastico, passate da una verifica automatica dei fatti e riviste a campione dalla redazione di Skooly (AI Act, Art. 50). Hai trovato un errore? Scrivi a supporto@skooly.it e lo correggiamo.