Compter les opérations
Compter les opérations élémentaires d'un code en fonction de la taille n : boucle simple, boucles successives, boucles imbriquées, boucle dépendante et boucle qui divise par deux.
- 25 cartes
- 6 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Opération élémentaire : de quoi s'agit-il ?
Voir la réponse
Opération dont le temps ne dépend pas de la taille des données : addition, comparaison, affectation, lecture d'une case d'un tableau.
On compte ce genre d'opération une fois chacune. Une instruction comme
x in tsur une liste n'en est pas une : elle compare jusqu'à n éléments.Qu'affiche ce programme ?
```python
c = 0
for i in range(5):
for j in range(5):
c += 1
print(c)`2510520
Voir la réponse
25La boucle interne fait 5 tours pour chacun des 5 tours de l'externe : 5 × 5 = 25. Additionner les tours (5 + 5) est l'erreur classique.
Une boucle de n tours avec un nombre fixe d'opérations par tour coûte environ … opérations ; deux boucles imbriquées de n tours chacune coûtent environ … opérations.
Voir la réponse
Une boucle de n tours avec un nombre fixe d'opérations par tour coûte environ n opérations ; deux boucles imbriquées de n tours chacune coûtent environ n² opérations.
Boucles imbriquées : on multiplie les nombres de tours (n × n). Boucles qui se suivent : on les additionne, n + n = 2n.
Taille de l'entrée : de quoi s'agit-il ?
Voir la réponse
Quantité qui mesure la grandeur des données à traiter, notée n : par exemple le nombre de cases d'un tableau.
Le coût d'un algorithme s'exprime en fonction de n. Pour un tableau de 20 cases, n vaut 20 ; pour un texte, c'est le nombre de caractères.