Cours Algorithmes Complet 🧠
Les 12 chapitres essentiels — complexité, tri, recherche, récursion, graphes et programmation dynamique
🏠 Hub Programmation
📦 Structures de données
🐍 Python
⚡ JavaScript
Introduction et complexité
Un algorithme est une suite finie d'instructions qui transforme une entrée en sortie pour résoudre un problème. Une recette de cuisine est un algorithme : des ingrédients (entrée), des étapes (instructions), un plat (sortie). En informatique, on mesure la qualité d'un algorithme par deux critères : sa vitesse (temps) et sa consommation mémoire (espace). Deux algorithmes peuvent résoudre le même problème — l'un en 1 seconde, l'autre en 1 heure. Savoir choisir le bon algorithme est la compétence fondamentale du développeur.
# Approche 1 : Recherche linéaire — O(n)
# On parcourt chaque élément un par un
def recherche_lineaire(liste, cible):
for element in liste:
if element == cible:
return True
return False
# Approche 2 : Recherche binaire — O(log n)
# On divise la liste en deux à chaque étape (liste triée)
def recherche_binaire(liste, cible):
gauche, droite = 0, len(liste) – 1
while gauche <= droite:
milieu = (gauche + droite) // 2
if liste[milieu] == cible:
return True
elif liste[milieu] < cible:
gauche = milieu + 1
else:
droite = milieu – 1
return False
# Sur 1 milliard d'éléments :
# Recherche linéaire : jusqu'à 1 000 000 000 comparaisons
# Recherche binaire : maximum 30 comparaisons (log₂ de 10⁹)
Notation Big O
| Big O | Nom | n = 1M | Exemple | Verdict |
|---|---|---|---|---|
| O(1) | Constant | 1 op | Accès array par index, hashmap get | 🟢 Idéal |
| O(log n) | Logarithmique | 20 ops | Recherche binaire, arbre BST | 🟢 Excellent |
| O(n) | Linéaire | 1M ops | Parcours de liste, recherche linéaire | 🟢 Bon |
| O(n log n) | Linéarithmique | 20M ops | Merge sort, quick sort, Tim sort | 🟡 Correct |
| O(n²) | Quadratique | 10¹² ops | Bubble sort, 2 boucles imbriquées | 🔴 Lent |
| O(2ⁿ) | Exponentiel | ∞ | Fibonacci récursif naïf, sous-ensembles | 🔴 Inutilisable |
| O(n!) | Factoriel | ∞ | Permutations, voyageur de commerce brut | 🔴 Impossible |
# O(n² + n + 1000) → O(n²) — n² domine quand n est grand
# Règle 2 : On ignore les constantes
# O(3n) → O(n) — la constante 3 disparaît
# Règle 3 : Boucles imbriquées = multiplication
for i in range(n): # O(n)
for j in range(n): # × O(n)
print(i, j) # = O(n²)
# Règle 4 : Boucles séquentielles = addition
for i in range(n): # O(n)
print(i)
for j in range(m): # + O(m)
print(j) # = O(n + m)
# Règle 5 : Diviser par 2 à chaque itération = O(log n)
while n > 1:
n = n // 2 # O(log n)
# Complexité spatiale (mémoire)
# O(1) = pas de mémoire supplémentaire (in-place)
# O(n) = copie de la liste (ex: merge sort)
# O(n²) = matrice n×n
Recherche
def recherche_lineaire(arr, cible):
for i, val in enumerate(arr):
if val == cible:
return i
return –1
# RECHERCHE BINAIRE — O(log n) — ⚠️ liste TRIÉE obligatoire
def recherche_binaire(arr, cible):
g, d = 0, len(arr) – 1
while g <= d:
m = (g + d) // 2
if arr[m] == cible:
return m
elif arr[m] < cible:
g = m + 1
else:
d = m – 1
return –1
# Variante : bisect (Python standard library)
import bisect
i = bisect.bisect_left(arr, cible) # Position d'insertion
found = i < len(arr) and arr[i] == cible
# Variante : trouver le premier élément ≥ cible
def lower_bound(arr, cible):
g, d = 0, len(arr)
while g < d:
m = (g + d) // 2
if arr[m] < cible:
g = m + 1
else:
d = m
return g
La recherche binaire est l'algorithme le plus important à maîtriser. Elle divise l'espace de recherche en deux à chaque itération. Applicable partout : tableaux triés, recherche de seuil, minimiser/maximiser une valeur, trouver une racine. Piège classique : (g + d) // 2 peut overflow en Java/C++ — utiliser g + (d – g) // 2.
Tri basique
# Idée : trouver le minimum, le placer au début, répéter
def tri_selection(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
# TRI PAR INSERTION — O(n²) pire cas, O(n) meilleur cas
# Idée : insérer chaque élément à sa bonne place
# ✅ Très rapide sur des données presque triées
def tri_insertion(arr):
for i in range(1, len(arr)):
cle = arr[i]
j = i – 1
while j >= 0 and arr[j] > cle:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = cle
# TRI À BULLES — O(n²) — le plus simple mais le plus lent
# Idée : comparer les éléments adjacents, échanger si mal placés
def tri_bulle(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n – i – 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped: # Optimisation : arrêter si déjà trié
break
Ces algorithmes O(n²) sont pédagogiques mais inutilisables en production sur de grandes données. Utilisez-les seulement pour comprendre les bases du tri. En pratique, utilisez les algorithmes O(n log n) du chapitre suivant. Seul le tri par insertion reste utile : il est optimal sur les petites listes (< 50 éléments) et les données presque triées — c'est pour ça que Tim sort (Python) l'utilise en interne.
Tri avancé
# 1. Diviser la liste en deux moitiés
# 2. Trier chaque moitié récursivement
# 3. Fusionner les deux moitiés triées
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
gauche = merge_sort(arr[:mid])
droite = merge_sort(arr[mid:])
return fusionner(gauche, droite)
def fusionner(g, d):
resultat = []
i = j = 0
while i < len(g) and j < len(d):
if g[i] <= d[j]: # <= pour la stabilité
resultat.append(g[i]); i += 1
else:
resultat.append(d[j]); j += 1
resultat.extend(g[i:])
resultat.extend(d[j:])
return resultat
# 1. Choisir un pivot
# 2. Placer les éléments < pivot à gauche, > pivot à droite
# 3. Récursion sur chaque côté
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # Pivot au milieu (évite O(n²) trié)
gauche = [x for x in arr if x < pivot]
milieu = [x for x in arr if x == pivot]
droite = [x for x in arr if x > pivot]
return quick_sort(gauche) + milieu + quick_sort(droite)
| Algorithme | Temps moyen | Pire cas | Espace | Stable | Usage |
|---|---|---|---|---|---|
| Merge sort | O(n log n) | O(n log n) | O(n) | ✅ Oui | Données sur disque, listes chaînées |
| Quick sort | O(n log n) | O(n²) | O(log n) | ❌ Non | Arrays en mémoire (le plus rapide en pratique) |
| Tim sort | O(n log n) | O(n log n) | O(n) | ✅ Oui | Python sorted(), Java Arrays.sort() |
| Heap sort | O(n log n) | O(n log n) | O(1) | ❌ Non | Mémoire limitée (in-place garanti) |
| Counting sort | O(n + k) | O(n + k) | O(k) | ✅ Oui | Petites valeurs entières (0 à k) |
En pratique, utilisez simplement sorted() en Python ou .sort() en JavaScript. Ces fonctions utilisent Tim sort (hybride merge sort + insertion sort), optimal dans 99% des cas. Comprenez merge sort et quick sort pour les entretiens techniques et pour savoir pourquoi les tris naïfs O(n²) sont mauvais.
Récursion
# 1. CAS DE BASE — quand s'arrêter (sinon boucle infinie)
# 2. CAS RÉCURSIF — appeler la fonction sur un sous-problème
# Factorielle : n! = n × (n-1)!
def factorielle(n):
if n <= 1: # Cas de base
return 1
return n * factorielle(n – 1) # Cas récursif
# Fibonacci NAÏF — O(2ⁿ) ❌ TERRIBLE
def fib_naif(n):
if n <= 1: return n
return fib_naif(n–1) + fib_naif(n–2) # Recalcule tout !
# Fibonacci avec MÉMOÏSATION — O(n) ✅
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
if n <= 1: return n
return fib_memo(n–1) + fib_memo(n–2)
# Fibonacci ITÉRATIF — O(n) temps, O(1) espace ✅✅
def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
Fibonacci illustre le piège de la récursion naïve : fib(50) naïf prend des millions d'années car il recalcule les mêmes valeurs des milliards de fois. fib_memo(50) prend des microsecondes. Si vous voyez une récursion avec des sous-problèmes qui se répètent → c'est de la programmation dynamique (chapitre 8).
Algorithmes de graphes
# Ex : réseau social, carte routière, dépendances de packages
# Représentation : liste d'adjacence (la plus courante)
graphe =
# BFS — Parcours en largeur — O(V + E)
# Explore niveau par niveau (file/queue)
# ✅ Chemin le plus court (graphe non pondéré)
from collections import deque
def bfs(graphe, depart):
visite = set()
queue = deque([depart])
visite.add(depart)
while queue:
noeud = queue.popleft()
print(noeud, end= » « )
for voisin in graphe[noeud]:
if voisin not in visite:
visite.add(voisin)
queue.append(voisin)
# DFS — Parcours en profondeur — O(V + E)
# Explore le plus loin possible (pile/stack)
# ✅ Détection de cycles, tri topologique
def dfs(graphe, noeud, visite=None):
if visite is None:
visite = set()
visite.add(noeud)
print(noeud, end= » « )
for voisin in graphe[noeud]:
if voisin not in visite:
dfs(graphe, voisin, visite)
# ✅ Chemin le plus court dans un graphe PONDÉRÉ (poids ≥ 0)
import heapq
def dijkstra(graphe, depart):
distances =
distances[depart] = 0
heap = [(0, depart)] # (distance, noeud)
while heap:
dist, noeud = heapq.heappop(heap)
if dist > distances[noeud]:
continue
for voisin, poids in graphe[noeud]:
nouvelle_dist = dist + poids
if nouvelle_dist < distances[voisin]:
distances[voisin] = nouvelle_dist
heapq.heappush(heap, (nouvelle_dist, voisin))
return distances
# Graphe pondéré (noeud → [(voisin, poids)])
graphe_p =
print(dijkstra(graphe_p, « A »))
# →
Programmation dynamique
La programmation dynamique (DP) résout un problème complexe en le décomposant en sous-problèmes qui se chevauchent. Au lieu de recalculer les mêmes résultats (comme Fibonacci naïf), on les stocke dans un tableau. Deux approches : top-down (récursion + mémoïsation) ou bottom-up (itératif, remplir un tableau du plus petit au plus grand). La DP transforme des problèmes exponentiels O(2ⁿ) en polynomiaux O(n²) ou O(n).
# Objets : [(poids, valeur)]
# Capacité du sac : W
def knapsack(objets, W):
n = len(objets)
# dp[i][w] = valeur max avec les i premiers objets et capacité w
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
poids, valeur = objets[i – 1]
for w in range(W + 1):
if poids > w:
dp[i][w] = dp[i–1][w] # Ne prend pas l'objet
else:
dp[i][w] = max(
dp[i–1][w], # Ne prend pas
dp[i–1][w – poids] + valeur # Prend l'objet
)
return dp[n][W]
objets = [(2, 3), (3, 4), (4, 5), (5, 6)] print(knapsack(objets, 8)) # → 10
# « ABCDE » et « ACE » → « ACE » (longueur 3)
# Utilisé dans : diff (git), bioinformatique, correcteurs
def lcs(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i–1] == s2[j–1]:
dp[i][j] = dp[i–1][j–1] + 1
else:
dp[i][j] = max(dp[i–1][j], dp[i][j–1])
return dp[m][n]
Algorithmes gloutons
# Rapide et simple, mais ne donne PAS toujours la solution optimale
# RENDU DE MONNAIE — Glouton fonctionne avec les pièces standard
def rendu_monnaie(montant, pieces=[200, 100, 50, 20, 10, 5, 2, 1]):
resultat = []
for piece in pieces:
while montant >= piece:
resultat.append(piece)
montant -= piece
return resultat
print(rendu_monnaie(167)) # → [100, 50, 10, 5, 2]
# PLANIFICATION D'ACTIVITÉS — trier par fin, prendre si compatible
def activites_max(activites):
# activites = [(debut, fin), …]
activites.sort(key=lambda x: x[1]) # Trier par heure de fin
resultat = [activites[0]]
for debut, fin in activites[1:]:
if debut >= resultat[–1][1]: # Pas de chevauchement
resultat.append((debut, fin))
return resultat
Glouton ≠ toujours optimal. Le rendu de monnaie avec les pièces [1, 3, 4] : pour 6, le glouton donne [4, 1, 1] (3 pièces) mais l'optimal est [3, 3] (2 pièces). Quand le glouton ne marche pas → programmation dynamique. Quand il marche, c'est plus rapide et plus simple que la DP.
Backtracking
# Si un chemin ne mène nulle part → revenir en arrière (backtrack)
# PERMUTATIONS — générer toutes les permutations
def permutations(arr):
resultat = []
def backtrack(chemin, restant):
if not restant:
resultat.append(chemin[:])
return
for i in range(len(restant)):
chemin.append(restant[i])
backtrack(chemin, restant[:i] + restant[i+1:])
chemin.pop() # ← Backtrack !
backtrack([], arr)
return resultat
# N-QUEENS — placer N reines sans conflit
def n_queens(n):
solutions = []
def backtrack(row, cols, diag1, diag2, board):
if row == n:
solutions.append([r[:] for r in board])
return
for col in range(n):
if col in cols or (row–col) in diag1 or (row+col) in diag2:
continue
board[row][col] = « Q »
backtrack(row+1, cols|, diag1|, diag2|, board)
board[row][col] = « . » # ← Backtrack
board = [[« . »] * n for _ in range(n)]
backtrack(0, set(), set(), set(), board)
return solutions
Le backtracking est la base de la résolution de puzzles : Sudoku, N-Queens, labyrinthe, mots croisés. Le pattern est toujours le même : faire un choix → explorer → annuler le choix (backtrack). Souvent O(n!) ou O(2ⁿ) — on accélère avec du pruning (élagage) en coupant les branches impossibles le plus tôt possible.
Entretiens techniques
| Pattern | Quand l'utiliser | Exemple |
|---|---|---|
| Two Pointers | Array trié, paire avec somme = cible | Two Sum (array trié), palindrome |
| Sliding Window | Sous-array/substring contigu(ë) optimal(e) | Max sum subarray, longest substring |
| HashMap/Set | Lookup O(1), comptage, doublons | Two Sum, anagrammes, fréquences |
| Binary Search | Donnée triée, chercher un seuil | Search in rotated array, Koko bananas |
| BFS / DFS | Graphes, arbres, matrices | Nombre d'îles, chemin le plus court |
| Dynamic Programming | Sous-problèmes qui se chevauchent | Climbing stairs, coin change, LCS |
| Backtracking | Explorer toutes les combinaisons | Permutations, N-Queens, Sudoku |
| Stack/Queue | Parenthèses, monotone stack | Valid parentheses, next greater element |
def two_sum_sorted(arr, cible):
g, d = 0, len(arr) – 1
while g < d:
s = arr[g] + arr[d] if s == cible:
return [g, d] elif s < cible:
g += 1
else:
d -= 1
return []
# SLIDING WINDOW — Somme max d'un sous-array de taille k — O(n)
def max_sum_k(arr, k):
window = sum(arr[:k])
max_sum = window
for i in range(k, len(arr)):
window += arr[i] – arr[i – k] # Glisser la fenêtre
max_sum = max(max_sum, window)
return max_sum
Bonnes pratiques
| Problème | Technique | Complexité |
|---|---|---|
| Chercher dans une liste triée | Recherche binaire | O(log n) |
| Trier des données | sorted() / Tim sort | O(n log n) |
| Chercher un élément | HashMap / Set | O(1) amorti |
| Chemin le plus court (non pondéré) | BFS | O(V + E) |
| Chemin le plus court (pondéré) | Dijkstra | O((V+E) log V) |
| Sous-problèmes qui se chevauchent | Programmation dynamique | Variable |
| Choix localement optimal suffit | Glouton | O(n log n) souvent |
| Explorer toutes les combinaisons | Backtracking | O(2ⁿ) ou O(n!) |
| Sous-array/substring contigu | Sliding window | O(n) |
| Paire dans un array trié | Two pointers | O(n) |
✅ À FAIRE
• Analyser la complexité AVANT de coder
• Commencer par la solution brute force
• Identifier le pattern (two pointers, DP, BFS…)
• Tester avec des cas limites (vide, 1 élément, max)
• Utiliser les structures de données standards (dict, set, deque)
• sorted() en Python = Tim sort O(n log n)
• bisect pour la recherche binaire
• heapq pour les files de priorité
• Apprendre les 8 patterns d'entretien
• Pratiquer sur LeetCode / HackerRank
❌ À ÉVITER
• Optimiser prématurément (d'abord correct, puis rapide)
• Boucles imbriquées inutiles (O(n²) → O(n) avec hashmap)
• Récursion sans cas de base (stack overflow)
• Fibonacci naïf O(2ⁿ) (utiliser mémoïsation/itératif)
• Tri à bulles en production (sorted() est toujours mieux)
• Ignorer la complexité spatiale (O(n²) mémoire = crash)
• Copier des listes dans une boucle (O(n²) caché)
• DFS récursif sur des données très profondes (pile Python limitée)
• Supposer que l'input est valide sans vérifier
• Confondre stable/instable (order matters)
🏠 Hub Programmation
📦 Cours Structures de données
🐍 Cours Python
⚡ Cours JavaScript
☕ Cours Java
