NSI · Première · Algorithmique et programmation
Terminaison et complexité
S’arrête-t-il ? Combien ça coûte ?
En bref
Deux questions se posent devant tout algorithme, et elles sont indépendantes : termine-t-il ?
Deux questions se posent devant tout algorithme, et elles sont indépendantes : termine-t-il ? et combien d'opérations coûte-t-il ?
La terminaison
| La boucle | Sa terminaison |
|---|---|
| Bornée (pour) | Assurée par construction : le nombre de tours est fixé d'avance |
| Non bornée (tant que) | À prouver |
Pour la prouver, on exhibe un variant : une quantité entière, positive, qui décroît strictement à chaque tour.
Une suite d'entiers positifs strictement décroissante ne peut pas être infinie : la boucle s'arrête.
La correction
Un algorithme peut terminer et rendre un résultat faux. On le prouve correct par un invariant de boucle : une propriété vraie avant la boucle, conservée par chaque tour, et qui, jointe à la condition de sortie, donne le résultat voulu.
| L'outil | La question à laquelle il répond |
|---|---|
| Variant | Est-ce que ça s'arrête ? |
| Invariant | Est-ce que c'est juste ? |
Les classes de complexité
On compte les opérations élémentaires en fonction de la taille n, et l'on ne retient que l'ordre de grandeur.
| La classe | Un exemple |
|---|---|
| Constant | Accéder à la case i d'un tableau |
| Logarithmique | Recherche dichotomique dans un tableau trié |
| Linéaire | Chercher un élément dans une liste non triée |
| n log n | Les bons algorithmes de tri |
| Quadratique | Tri par sélection, tri par insertion : deux boucles imbriquées |
| Exponentiel | Essayer toutes les combinaisons : impraticable au-delà de quelques dizaines d'éléments |
Ce que cela veut dire concrètement
| Sur un million d'éléments | Le nombre d'opérations | Le temps |
|---|---|---|
| Algorithme linéaire | Un million | Une seconde |
| Algorithme quadratique | Mille milliards | Des semaines |
Améliorer l'algorithme bat toujours l'achat d'une machine plus rapide.
Pire cas, meilleur cas
| Le cas de la recherche séquentielle | Son coût |
|---|---|
| L'élément est en tête | Une comparaison |
| L'élément est absent | n comparaisons |
On raisonne d'ordinaire sur le pire cas : c'est la seule garantie, et c'est lui qui sert à dimensionner un système.
Teste-toi
6 questions pour vérifier
Touche une réponse : la correction s’affiche tout de suite.
1.Qu’est-ce qu’un variant de boucle ?
2.Quelle est la complexité d’une recherche dichotomique dans un tableau trié ?
3.Un algorithme qui termine rend nécessairement un résultat correct.
4.Quelle est la complexité de deux boucles imbriquées parcourant chacune n éléments ?
5.Pourquoi raisonne-t-on d’ordinaire sur le pire cas ?
6.Combien d’opérations un algorithme quadratique effectue-t-il sur un million d’éléments ?
0 / 6 questions
Dans l’app, ce chapitre a son quiz complet, chronométré, et tes erreurs reviennent au bon moment pour ne plus les refaire.
La fiche de révision, sur une page
Tout « Arrêt et complexité » sur une seule page A4 illustrée : l’essentiel, les pièges et un mini-test. Elle se débloque dans l’app avec des gemmes — et ton compte gratuit en offre assez pour tes trois premières fiches.
