Calculer une complexité
Compter les opérations d'un code itératif : instructions en séquence, boucle simple, boucles imbriquées, boucle qui divise par deux, appel caché dans une boucle, meilleur et pire cas, mémoire utilisée.
- 19 cartes
- 3 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
Quelques cartes du deck
Opération élémentaire : de quoi s'agit-il ?
Voir la réponse
Instruction dont le coût ne dépend pas de la taille des données : une affectation, une comparaison, une addition, un accès à une case de tableau.
C'est l'unité qu'on compte. Attention aux instructions qui n'en sont pas :
x in liste,liste.count(x)oumax(liste)parcourent toute la liste et coûtent O(n).Quelle est la complexité en temps de cette fonction ?
```python
def f(n):
c = 0
for i in range(n):
for j in range(n):
c += 1
for k in range(n):
c += 1
return c`- O(n²)
- O(n³)
- O(n)
- O(n log n)
Voir la réponse
O(n²)
Le bloc double fait n² incréments, la boucle finale n : n² + n opérations, dont le terme dominant est n². Les boucles ne s'enchaînent pas en n³ car la dernière n'est pas imbriquée : son coût s'ajoute au lieu de se multiplier.
Deux boucles de n tours : si elles sont imbriquées, le corps s'exécute … fois ; si elles se suivent, il s'exécute … fois en tout, soit O(n).
Voir la réponse
Deux boucles de n tours : si elles sont imbriquées, le corps s'exécute n² fois ; si elles se suivent, il s'exécute 2n fois en tout, soit O(n).
Boucles imbriquées : les nombres de tours se multiplient. Boucles à la suite : ils s'additionnent.
Pire cas : de quoi s'agit-il ?
Voir la réponse
Coût maximal d'un algorithme sur toutes les entrées possibles d'une taille n donnée.
C'est une garantie : aucune entrée de taille n ne coûtera davantage. Pour une recherche séquentielle, c'est l'élément en dernière place ou absent.
Combien de tours fait cette boucle, en fonction de n ?
```python
i = 1
while i < n:
i = i * 2`- O(n)
- O(log n)
- O(√n)
- O(n log n)
Voir la réponse
O(log n)
i vaut 1, 2, 4, 8… : il double à chaque tour et atteint n après environ log₂ n tours. Un indice qui avance de 1 donnerait O(n), mais ici il saute de plus en plus loin.