Ton application devient lente
Ton application cherche un contact. Avec 20 contacts, elle répond tout de suite. Avec 20 000, elle met un temps fou.
Faut-il acheter un téléphone plus rapide ? Peut-être. Mais souvent, c'est la méthode qui est en cause.
Dans cette leçon, tu apprends à mesurer une méthode. Pas avec une montre : en comptant ses étapes.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Coût | Le nombre d'étapes dont un algorithme a besoin. | 8 lectures pour une liste de 8 cases |
| Comparaison | Regarder si une valeur est égale, plus petite ou plus grande qu'une autre. | liste[i] == valeur |
| Taille | Le nombre de valeurs que l'algorithme doit traiter. | Une liste de 1000 prénoms |
| Pire cas | La situation où l'algorithme fait le plus de travail. | Le nom cherché est absent |
| Mesurer | Compter avec une variable qui augmente de 1 à chaque étape. | lectures = lectures + 1 |
| Lent | Un algorithme dont le travail grossit très vite avec la taille. | Trier une grande liste par sélection |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : devine le coût
À toi de jouer
À toi : devine le coût
3 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.
Pourquoi compter les étapes ?
Le temps en secondes dépend de la machine. Ton téléphone et un vieil ordinateur ne vont pas à la même vitesse.
Le nombre d'étapes ne dépend pas de la machine. C'est lui qui dit si une méthode est bonne. On le compte surtout au pire cas, car c'est là qu'on attend le plus.
À toi : compter les lectures
def lectures_pire_cas(taille):
liste = []
for nombre in range(taille):
liste.append(nombre)
lectures = 0
for indice in range(len(liste)):
lectures = lectures + 1 # une lecture de plus
if liste[indice] == -1: # -1 n'est jamais là
return lectures
return lectures
for taille in [4, 8, 16, 1000]:
print("Liste de", taille, "cases :", lectures_pire_cas(taille), "lectures")
# Quand la liste double, que fait le nombre de lectures ?
Exemple travaillé : lire case par case
| Taille de la liste | Lectures au pire |
|---|---|
| 4 | 4 |
| 8 | 8 |
| 16 | 16 |
| 1000 | 1000 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : compter les coups de la dichotomie
def coups_pire_cas(taille):
liste = []
for nombre in range(taille):
liste.append(nombre)
debut = 0
fin = len(liste) - 1
coups = 0
while debut <= fin:
milieu = (debut + fin) // 2
coups = coups + 1
if liste[milieu] < taille: # taille est plus grand que tout
debut = milieu + 1
else:
fin = milieu - 1
return coups
for taille in [4, 8, 16, 1000]:
print("Liste de", taille, "cases :", coups_pire_cas(taille), "coups")
# Quand la liste double, que fait le nombre de coups ?
Exemple travaillé : chercher en coupant en deux
| Taille de la liste | Coups au pire |
|---|---|
| 4 | 3 |
| 8 | 4 |
| 16 | 5 |
| 1000 | 10 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Deux méthodes face à face
Lire case par case : si la liste double, le travail double.
Couper en deux : si la liste double, on ajoute un seul coup. Sur 1000 cases, 10 coups. Sur 2000, 11.
On dit que la deuxième méthode est rapide et que la première est lente quand la liste devient grande.