#Complessità computazionaleIn questo capitolo parleremo di complessità computazionale, ovvero un modo per misurare approssimativamente quante operazioni vengono eseguite dal nostro programma al variare della dimensione dell’input. Come abbiamo visto nel capitolo introduttivo sulle olimpiadi, i problemi hanno spesso un limite di tempo (e di memoria) da rispettare. Risulta quindi molto utile essere in grado di confrontare due programmi, stimare quale sia più veloce e quante operazioni verranno svolte.
Introduciamo un po’ di notazione: con 𝒪︀(𝑔(𝑛)) indichiamo che il numero di operazioni è limitato superiormente da una quantità proporzionale a 𝑔(𝑛), quando 𝑛 diventa grande. Nota che 𝑔(𝑛) non indica il numero esatto di operazioni, ma dà una stima di quanto velocemente possa crescere il numero di operazioni al variare di 𝑛.
Per esempio, per un algoritmo che esegue 3𝑛+17 operazioni usiamo 𝑔(𝑛)=𝑛, e quindi 𝒪︀(𝑛): il 3 è un fattore costante e il 17 è un termine costante. Entrambi cambiano il numero esatto di operazioni, ma non il modo in cui questo numero cresce. Questa descrizione viene chiamata complessità computazionale o complessità asintotica.1
Ad esempio:
•𝒪︀(1): il numero di operazioni è indipendente da 𝑛. Per esempio, leggere il primo elemento di un vettore ha complessità 𝒪︀(1).•𝒪︀(𝑛): il numero di operazioni cresce linearmente rispetto al numero di elementi. Per esempio, invertire un vettore ha complessità 𝒪︀(𝑛) perché ci sono 𝑛 elementi da spostare.•𝒪︀(𝑛2): il numero di operazioni cresce come 𝑛2. Per esempio, confrontare ogni elemento di un vettore con tutti gli altri richiede circa 𝑛2 operazioni.Nota che consideriamo sempre il massimo numero possibile di operazioni perché due input della stessa dimensione possono richiedere quantità diverse di lavoro. Ad esempio, supponiamo di avere un algoritmo che ha complessità 𝒪︀(𝑛2) solo quando 𝑛 è multiplo di 10, e 𝒪︀(𝑛) in tutti gli altri casi: diremo comunque che l’algoritmo ha complessità 𝒪︀(𝑛2).
Per completezza, forniamo una definizione più formale di complessità computazionale (facoltativa, ma interessante e utile per comprendere meglio l’argomento):
#Definizione formaleSia 𝑔(𝑛) il massimo numero di operazioni di un algoritmo sugli input di dimensione 𝑛.
Dire che 𝑔(𝑛)∈𝒪︀(𝑓(𝑛)) significa che il rapporto tra 𝑔(𝑛) e 𝑓(𝑛) rimane limitato quando 𝑛 diventa molto grande. Supponiamo che 𝑓(𝑛) sia positiva per 𝑛 sufficientemente grande. Formalmente,
lim sup𝑛→∞𝑔(𝑛)𝑓(𝑛)<∞.
Nota come, secondo questa definizione, sia corretto affermare che 𝑛2∈𝒪︀(𝑛3), perché
lim𝑛→∞𝑛2𝑛3=0.
In generale, tra più limiti superiori corretti si preferisce quello più piccolo e più preciso.
Per esempio, 𝑛, 𝑛+4 e 3𝑛+17 appartengono tutte alla classe 𝒪︀(𝑛). Anche 42+(−1)𝑛 appartiene a 𝒪︀(𝑛), ma appartiene anche a 𝒪︀(1), perché vale sempre 41 oppure 43.
#EsempiDato un array di 𝑛 interi 𝑎0,𝑎1,…,𝑎𝑛−1, consideriamo il problema di trovare la massima somma di un sottoarray2 (anche vuoto) di 𝑎.
Un primo approccio implementa né più né meno la definizione del problema. Il programma a destra itera su tutti i sottoarray, ne calcola la somma e sceglie il valore massimo. Il numero totale di iterazioni è proporzionale a 𝑛3, quindi il codice a destra ha complessità 𝒪︀(𝑛3).ll ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
ll sum = 0;
for (int k = i; k <= j; k++)
sum += a[k];
ans = max(ans, sum);
}
}
L’approccio precedente si può migliorare notando che la somma del sottoarray 𝑎𝑖,…,𝑎𝑗+1 si ottiene con un’operazione a partire dalla somma del sottoarray 𝑎𝑖,…,𝑎𝑗. Questa implementazione elimina il ciclo for più interno, abbassando la complessità a 𝒪︀(𝑛2).ll ans = 0;
for (int i = 0; i < n; i++) {
ll sum = 0;
for (int j = i; j < n; j++) {
sum += a[j];
ans = max(ans, sum);
}
}
Possiamo fare meglio di così e risolvere il problema in tempo lineare. Posta 𝑝𝑖≔𝑎0+…+𝑎𝑖 la somma del prefisso che termina con 𝑎𝑖, vale 𝑎𝑖+…+𝑎𝑗=𝑝𝑗−𝑝𝑖−1. A 𝑗 fissato, la somma 𝑝𝑗−𝑝𝑖−1 è massima quando 𝑝𝑖−1 è minima. Una soluzione itera su tutti i possibili 𝑗, mantenendo la somma prefissa corrente e il minimo tra le somme prefisse precedenti. Questo approccio ha complessità 𝒪︀(𝑛).ll ans = 0;
ll prf = 0, min_prf = 0;
for (int i = 0; i < n; i++) {
prf += a[i];
min_prf = min(min_prf, prf);
ans = max(ans, prf - min_prf);
}
Per il momento non serve capire a fondo gli algoritmi appena esposti: basta comprendere che possono esistere approcci diversi per rispondere a una stessa richiesta, e alcuni sono molto più efficienti di altri.
Non sempre c’è un’unica soluzione migliore, ma valutarne la complessità permette di capire quale strategia adottare sulla base delle limitazioni del problema.
Osserva infine che lo stesso tipo di analisi si può applicare anche alla memoria utilizzata, oltre che al numero di operazioni eseguite.
Determina per esercizio la complessità dei seguenti pezzi di codice.
for (int i = 0; i < n; i++) {
int cur = i;
while (cur != 0)
cur /= 2;
}
int x = 0;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j += i)
x++;
}
#Ultimi consigli e casi notevoliSpesso ci si trova a dover stimare la complessità di un algoritmo in situazioni in cui la struttura di alcuni cicli rende non evidente quanto il numero di iterazioni cresca velocemente. Ecco alcuni dei casi più comuni:
•Iterare 𝑁 volte, poi 𝑁2, poi 𝑁4 e così via, dimezzando ogni volta il numero di iterazioni, richiede 𝒪︀(𝑁) operazioni perché 𝑁+𝑁2+𝑁4+𝑁8+…+1≈2𝑁.
•Iterare 𝑁+𝑁2+𝑁3+𝑁4+…+1 volte richiede 𝒪︀(𝑁log𝑁) operazioni, dal momento che ∑𝑁𝑖=1𝑁𝑖≈ 𝑁ln𝑁.
for (int i = 1; i <= N; i++) {
for (int j = i; j <= N; j += i) {
// Questo blocco viene eseguito O(N log N) volte
}
}
•Altri fatti utili da conoscere sono che il numero di fattori primi di un numero è 𝒪︀(log𝑁) e che il numero di primi minori di 𝑁 è 𝒪︀(𝑁ln𝑁).In generale puoi tenere a mente la tabella che segue come riferimento per la complessità target data la grandezza di 𝑁.
Limite di 𝑁
Complessità Attesa
Esempi Tipici di Algoritmi
𝑁≤11
𝒪︀(𝑁!)
Permutazioni, Ricerca completa
𝑁≤22
𝒪︀(2𝑁⋅𝑁)
Bitmask DP
𝑁≤100
𝒪︀(𝑁4) o 𝒪︀(𝑁3)
Floyd-Warshall, DP cubiche o quartiche
𝑁≤1000
𝒪︀(𝑁2) o 𝒪︀(𝑁2log𝑁)
DP quadratiche, Grafi densi
𝑁≤105 o 2⋅105
𝒪︀(𝑁log𝑁)
Ordinamento, Segment Tree, Dijkstra
𝑁≤106 o 107
𝒪︀(𝑁) o 𝒪︀(𝑁loglog𝑁)
Two Pointers, Sliding Window, Crivello
𝑁≤1018
𝒪︀(log𝑁) o 𝒪︀(1)
Ricerca Binaria sull’output, Matematica
Non preoccuparti se non conosci gli algoritmi citati nella tabella: li imparerai man mano con la lettura di questa guida. In generale puoi tenere a mente che in un secondo si possono eseguire circa 108 operazioni elementari.
1Classicamente questa si esprime in numero di bit. Nel nostro contesto il significato sarà sempre chiaro.2Ricorda che un sottoarray di un array 𝑎=[𝑎0,…,𝑎𝑛−1] è un array del tipo [𝑎𝑙,…,𝑎𝑟] per qualche scelta di 0≤𝑙≤ 𝑟<𝑛.