Rilasciato · in miglioramento
Algorithm
Impara ad analizzare con la notazione O grande come crescono tempo e memoria di un algoritmo al crescere dell'input, e a verificarlo con misure reali.
L'analisi della complessità descrive quanto crescono il tempo e la memoria richiesti da un algoritmo quando l'input diventa più grande. Invece dei secondi, che dipendono da hardware e linguaggio, conta le operazioni elementari in funzione della dimensione n dell'input e tiene solo il termine dominante. Il risultato si esprime in notazione asintotica: O grande per un limite superiore, Omega grande per un limite inferiore e Theta grande per un limite stretto.
È importante perché, quando i dati crescono, la differenza tra ordini di crescita supera qualsiasi fattore costante. Una routine O(n²) che va bene con mille elementi può richiedere ore con un milione, mentre una O(n log n) termina in pochi secondi. La complessità serve a scegliere le strutture dati, interpretare i limiti di input di un esercizio di programmazione, individuare costi nascosti durante la code review e stimare se un sistema scalerà.
Inizia contando le operazioni di cicli semplici e imparando le classi più comuni: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) e O(n!). Passa poi a caso migliore, medio e peggiore, analisi ammortizzata, complessità spaziale e risoluzione delle ricorrenze con il teorema master. Verifica sempre il ragionamento con un esperimento di raddoppio: misura il codice con n e con 2n e confronta il rapporto.
O, Ω e Θ danno limiti superiori, inferiori e stretti alla crescita, ignorando le costanti e i termini di ordine inferiore.
I blocchi in sequenza sommano i costi, i cicli annidati li moltiplicano e dimezzare il problema a ogni passo porta a un logaritmo.
Distribuisce il costo su un'intera sequenza di operazioni: per questo aggiungere a un array dinamico è O(1) anche se ogni tanto bisogna copiare tutto.
Contano anche la memoria ausiliaria e la profondità della ricorsione, e il teorema master risolve le ricorrenze del divide et impera.
Lo script risolve lo stesso problema in due modi: controllando tutte le coppie, oppure con un solo passaggio che ricorda in un dizionario i valori già visti. Misurando entrambi con timeit per n = 500, 1.000 e 2.000, ogni raddoppio rende la versione quadratica circa quattro volte più lenta e quella lineare circa due volte.
complexity.py
import timeit
def two_sum_quadratic(nums, target):
"""O(n^2): try every pair."""
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return i, j
return None
def two_sum_linear(nums, target):
"""O(n) on average: remember values already seen."""
seen = {}
for j, x in enumerate(nums):
i = seen.get(target - x)
if i is not None:
return i, j
seen.setdefault(x, j)
return None
print(two_sum_quadratic([8, 3, 11, 5, 2], 13), two_sum_linear([8, 3, 11, 5, 2], 13))
for n in (500, 1_000, 2_000):
nums = list(range(0, 2 * n, 2)) # even numbers only, so no pair sums to -1
slow = timeit.timeit(lambda: two_sum_quadratic(nums, -1), number=3) / 3
fast = timeit.timeit(lambda: two_sum_linear(nums, -1), number=3) / 3
print(f"n={n:>5} O(n^2) {slow * 1000:8.2f} ms O(n) {fast * 1000:6.3f} ms")
python complexity.pySei capitoli che ti accompagnano dall'installazione ai concetti chiave di Analisi della complessità.
Fai domande, condividi la tua esperienza e scambia opinioni su Analisi della complessità.
Ancora nessuna discussione. Avvia la prima.
0 commenti
Accedi · Accedi per lasciare un commento.
Scrivi tu il primo commento.