Les algorithmes sont au cœur de la NSI Terminale. Maîtriser la complexité, les algorithmes de tri et les preuves formelles est indispensable pour réussir le bac.
La complexité temporelle mesure le nombre d'opérations d'un algorithme en fonction de la taille n de l'entrée. Notation O : O(1) = constant, O(log n) = logarithmique, O(n) = linéaire, O(n2) = quadratique. Elle caractérise le comportement dans le pire cas.
Question probable
Qu'est-ce que la complexité temporelle d'un algorithme et comment la calculer ?
Réponse
→La complexité mesure le nombre d'opérations en fonction de n. O(1) : accès direct (tableau par indice). O(n) : parcours complet d'une liste. O(n2) : deux boucles imbriquées (tri par insertion). O(log n) : dichotomie (on divise par 2 à chaque étape). On retient le terme dominant : 3n2 + 2n est O(n2). La complexité spatiale mesure la mémoire utilisée. Un algorithme O(n log n) est préférable à O(n2) pour de grandes données.
Mnémotechnique
1 < log n < n < n log n < n2 < 2ⁿ. "Constant Log Linéaire LogLinéaire Quadratique Exponentiel." O = ordre de grandeur du pire cas.
1 / 5
NSI
Algorithmes de tri
Définition
Le tri par insertion parcourt le tableau et insère chaque élément à sa bonne place dans la partie déjà triée — complexité O(n2) dans le pire cas. Le tri fusion (merge sort) divise le tableau en deux, trie récursivement chaque moitié et fusionne — complexité O(n log n).
Question probable
Comparez le tri par insertion et le tri fusion.
Réponse
→Tri par insertion : on parcourt de gauche à droite. Pour chaque élément, on le déplace vers la gauche jusqu'à sa bonne position. Simple à coder, efficace pour des listes presque triées, mais O(n2) au pire. Tri fusion : on divise la liste en deux (jusqu'à des listes de 1 élément), puis on fusionne en comparant les éléments. Toujours O(n log n) mais nécessite O(n) mémoire supplémentaire. Pour n grand, le tri fusion est bien plus rapide que le tri par insertion.
Mnémotechnique
Insertion = O(n2) = simple mais lent. Fusion = O(n log n) = divise-et-règne. Insertion pour petits tableaux, Fusion pour grands.
2 / 5
NSI
Recherche dichotomique
Définition
Algorithme de recherche dans un tableau trié. On compare l'élément cherché avec le milieu du tableau : si inférieur, on cherche dans la moitié gauche ; si supérieur, dans la moitié droite. On répète jusqu'à trouver ou constater l'absence. Complexité O(log n).
Question probable
Décrivez l'algorithme de recherche dichotomique et justifiez sa complexité.
Réponse
→Prérequis : le tableau doit être trié. On part des indices gauche=0 et droite=n-1. On calcule milieu=(gauche+droite)//2. Si tab[milieu]==cible : trouvé. Si tab[milieu]droite. Complexité : à chaque étape on divise l'espace de recherche par 2 → log₂(n) étapes → O(log n). Pour n=1 000 000, au plus 20 étapes. Beaucoup plus efficace que la recherche linéaire O(n).
Mnémotechnique
Dichotomie = couper en deux. Trier d'abord ! O(log n) : log₂(1 000 000) ≈ 20. "Téléphone : p. 500 → p. 250 ou p. 750."
3 / 5
NSI
Preuve de terminaison
Définition
Pour prouver qu'un algorithme (notamment une boucle) se termine toujours, on utilise un variant de boucle : une expression entière qui (1) est toujours positive ou nulle, et (2) décroît strictement à chaque itération. Quand elle atteint 0, la boucle s'arrête.
Question probable
Comment prouver qu'un algorithme itératif se termine ?
Réponse
→On définit un variant de boucle v : une expression à valeurs entières naturelles. On montre que v ≥ 0 avant chaque itération et que v diminue strictement à chaque tour de boucle. Puisque v est entier, positif et décroît, il atteint 0 en un nombre fini d'étapes. Exemple : recherche dichotomique, variant = droite - gauche. À chaque étape, cet intervalle est divisé par 2 → la boucle se termine en O(log n) itérations.
Mnémotechnique
Variant = entier, ≥ 0, strict. décroît. Atteint 0 → boucle finie. "V pour Vérification de fin."
4 / 5
NSI
Preuve de correction (invariant de boucle)
Définition
Un invariant de boucle est une propriété qui (1) est vraie avant d'entrer dans la boucle (initialisation), (2) reste vraie après chaque itération si elle l'était avant (conservation), et (3) permet de conclure sur la correction de l'algorithme à la sortie de la boucle.
Question probable
Qu'est-ce qu'un invariant de boucle ? Illustrez avec un exemple.
Réponse
→Un invariant est une propriété P maintenue tout au long de la boucle. Méthode : 1. Initialisation : P est vraie avant la première itération. 2. Conservation : si P est vraie au début d'une itération, elle reste vraie à la fin. 3. Conclusion : quand la boucle se termine (variant = 0), l'invariant + la condition de sortie permettent de conclure. Exemple (tri par insertion) : invariant = "les i premiers éléments sont triés entre eux". À la fin (i=n), les n éléments sont triés.