Codzy

Complessità in tempo e in spazio

La complessità misura come cresce il tempo (o la memoria) di un algoritmo quando i dati aumentano. Si scrive con la notazione O grande: O(1) costante, O(log n) come la ricerca binaria, O(n) un ciclo semplice, O(n²) due cicli annidati.

La complessità in spazio misura la memoria usata. Spesso si scambia un po' di memoria con molta velocità: cercare in una lista è O(n), ma cercare in un set o in un dict è in media O(1).

def count_steps(n):
    steps = 0
    for i in range(n):
        for j in range(n):
            steps += 1
    return steps

for n in [10, 20, 40]:
    print(n, "->", count_steps(n), "steps")

names = set(["Ana", "Ben", "Chloe"])
print("Ben" in names)

Inizia la lezione