Complexité en temps et en espace
La complexité mesure comment le temps (ou la mémoire) d'un algorithme augmente quand les données grossissent. On l'écrit avec la notation grand O : O(1) constant, O(log n) comme la recherche dichotomique, O(n) une simple boucle, O(n²) deux boucles imbriquées.
La complexité en espace mesure la mémoire utilisée. Souvent, on échange un peu de mémoire contre beaucoup de vitesse : chercher dans une liste est en O(n), mais chercher dans un set ou un dict est en moyenne en 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)