Fiche résumé – Algorithmique appliquée

Chapitre 25 | BTS | Mathématiques

Dernière mise à jour : 21 juin 2026

L'essentiel :

Recherche : séquentielle \(O(n)\) sur tout tableau ; dichotomique \(O(\log n)\) sur tableau trié.
Tris : bulles / insertion / sélection en \(O(n^2)\) ; tri rapide et tri fusion en \(O(n\log n)\).
Structures : pile = LIFO (dernier entré, premier sorti), file = FIFO (premier entré, premier sorti).
Un algorithme récursif a toujours un cas de base + un appel sur un problème plus petit.
Échelle de complexité : \(O(1)\ll O(\log n)\ll O(n)\ll O(n\log n)\ll O(n^2)\ll O(2^n)\).

Définitions clés

Définition

Notation Big-O : \(O(f(n))\) décrit la croissance asymptotique du nombre d'opérations selon la taille \(n\). On ne garde que le terme dominant : \(3n^2+5n+2\in O(n^2)\).

Définition

Pile (LIFO) : push / pop au sommet. File (FIFO) : enqueue à l'arrière, dequeue à l'avant.

Définition

Récursivité : fonction qui s'appelle elle-même, avec un cas de base (arrêt) et un appel sur un problème de taille strictement plus petite (sinon stack overflow).

Comparaison des algorithmes de tri

Algorithme	Meilleur	Moyen	Pire	Stable
Tri à bulles	\(O(n)\)	\(O(n^2)\)	\(O(n^2)\)	Oui
Tri par insertion	\(O(n)\)	\(O(n^2)\)	\(O(n^2)\)	Oui
Tri par sélection	\(O(n^2)\)	\(O(n^2)\)	\(O(n^2)\)	Non
Tri rapide	\(O(n\log n)\)	\(O(n\log n)\)	\(O(n^2)\)	Non
Tri fusion	\(O(n\log n)\)	\(O(n\log n)\)	\(O(n\log n)\)	Oui
Python `sort()`	\(O(n)\)	\(O(n\log n)\)	\(O(n\log n)\)	Oui

Classes de complexité

\(O(1)\)	\(O(\log n)\)	\(O(n)\)	\(O(n\log n)\)	\(O(n^2)\)	\(O(2^n)\)
accès indice	dichotomie	parcours	tri rapide / fusion	tris simples	Fibonacci naïf

Repères à connaître

Dichotomie et récursivité \[\text{Dichotomie}:\ \text{au plus }\lceil\log_2 n\rceil\text{ comparaisons}\quad(n=10^6\Rightarrow 20)\] \[\text{Hanoï}:\ 2^n-1\text{ déplacements}\qquad\text{Fibonacci naïf}:\ T(n)\approx 2^n\]

Coûts des structures (tableau vs liste chaînée)

Accès par indice : tableau \(O(1)\), liste chaînée \(O(n)\).
Insertion en tête : tableau \(O(n)\), liste chaînée \(O(1)\).
File efficace : collections.deque (popleft en \(O(1)\)).

Méthodes

Méthode Analyser et écrire un algorithme

Comprendre le problème : entrées, résultat, contraintes.
Choisir la structure : accès rapide → tableau ; LIFO → pile ; FIFO → file/deque.
Choisir l'algorithme : trié → dichotomique ; petit tableau → insertion ; grand → tri rapide / sorted().
Tester les cas limites : vide, un élément, déjà trié, trié à l'envers.
Analyser la complexité \(O(\cdot)\) et juger si elle est acceptable.

Erreurs fréquentes

Attention

❌ Lancer une recherche dichotomique sur un tableau non trié.

✅ La dichotomie exige un tableau trié, sinon le résultat est faux.

❌ Utiliser list.pop(0) dans une boucle pour gérer une file.

✅ C'est \(O(n)\) par appel (\(O(n^2)\) au total) : utiliser collections.deque et popleft().

❌ Utiliser la version récursive naïve de Fibonacci pour de grands \(n\).

✅ Elle est en \(O(2^n)\) : préférer l'itératif ou la mémoïsation (\(O(n)\)).

❌ Oublier le cas de base d'une fonction récursive.

✅ Sans condition d'arrêt, on provoque une récursion infinie (stack overflow).