Cours Algorithmes Complet 🧠

# 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⁹)

# 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 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

# 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

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

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)

# 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

# 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)

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 »))
# →

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

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]

# 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

# 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

# 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