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)