Algorithmique

🎯 Introduction

L'algorithmique est l'étude des algorithmes : leur conception, leur correction (font-ils bien ce qu'on veut ?) et leur efficacité (combien de temps et de mémoire consomment-ils ?). Au bac NSI, on évalue surtout la complexité temporelle et les grands algorithmes classiques.

📊 Complexité algorithmique

La complexité temporelle mesure le nombre d'opérations en fonction de la taille de l'entrée n. On utilise la notation grand O pour exprimer le pire cas.

Comment calculer la complexité ?

# O(n) : une boucle simple
def somme(lst):
    total = 0
    for x in lst:   # n itérations
        total += x   # O(1)
    return total    # → O(n) au total

# O(n²) : deux boucles imbriquées
def paires(lst):
    for i in range(len(lst)):       # n itérations
        for j in range(len(lst)):   # n itérations
            print(lst[i], lst[j])   # → O(n²)

# O(log n) : on divise par 2 à chaque étape
def log_n(n):
    k = 0
    while n > 1:
        n = n // 2   # on divise par 2
        k += 1
    return k         # → O(log n)

🔀 Algorithmes de tri

def tri_insertion(lst):
    for i in range(1, len(lst)):
        cle = lst[i]
        j = i - 1
        while j >= 0 and lst[j] > cle:
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = cle
    return lst

# Complexité : O(n²) pire cas, O(n) meilleur cas (déjà trié)

def tri_selection(lst):
    n = len(lst)
    for i in range(n):
        idx_min = i
        for j in range(i + 1, n):
            if lst[j] < lst[idx_min]:
                idx_min = j
        lst[i], lst[idx_min] = lst[idx_min], lst[i]
    return lst

# Complexité : O(n²) dans tous les cas

def fusion(g, d):
    res, i, j = [], 0, 0
    while i < len(g) and j < len(d):
        if g[i] <= d[j]:
            res.append(g[i]); i += 1
        else:
            res.append(d[j]); j += 1
    return res + g[i:] + d[j:]

def tri_fusion(lst):
    if len(lst) <= 1:
        return lst
    m = len(lst) // 2
    return fusion(tri_fusion(lst[:m]),
                  tri_fusion(lst[m:]))

# Complexité : O(n log n) dans tous les cas

def tri_rapide(lst):
    if len(lst) <= 1:
        return lst
    pivot = lst[len(lst) // 2]
    gauche  = [x for x in lst if x < pivot]
    milieu  = [x for x in lst if x == pivot]
    droite  = [x for x in lst if x > pivot]
    return tri_rapide(gauche) + milieu + tri_rapide(droite)

# Complexité : O(n log n) en moyenne, O(n²) au pire cas

Tableau récapitulatif des tris

* Version en place possible mais la version Python ci-dessus ne l'est pas.

🔍 Recherche dichotomique

Sur un tableau trié, on compare l'élément du milieu avec la cible. On réduit l'intervalle de recherche de moitié à chaque étape → O(log n).

def recherche_dicho(lst, cible):
    """Renvoie l'indice de cible ou -1 si absent."""
    gauche, droite = 0, len(lst) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if lst[milieu] == cible:
            return milieu
        elif lst[milieu] < cible:
            gauche = milieu + 1   # chercher à droite
        else:
            droite = milieu - 1   # chercher à gauche
    return -1

# Exemple
lst = [2, 5, 8, 12, 16, 23, 38, 56]
print(recherche_dicho(lst, 23))   # → 5
print(recherche_dicho(lst, 10))   # → -1

Version récursive

def dicho_rec(lst, cible, g=0, d=None):
    if d is None: d = len(lst) - 1
    if g > d: return -1          # cas de base : non trouvé
    m = (g + d) // 2
    if lst[m] == cible: return m  # cas de base : trouvé
    if lst[m] < cible:
        return dicho_rec(lst, cible, m + 1, d)
    return dicho_rec(lst, cible, g, m - 1)

🔄 Récursivité

Une fonction est récursive si elle s'appelle elle-même. Toute fonction récursive doit avoir un cas de base (condition d'arrêt) et un appel récursif qui se rapproche du cas de base.

# Factorielle : n! = n × (n-1)!
def factorielle(n):
    if n <= 1:            # cas de base
        return 1
    return n * factorielle(n - 1)  # appel récursif

# Suite de Fibonacci
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)  # Complexité : O(2ⁿ) !

# Visualiser la pile d'appels pour fib(4) :
# fib(4) → fib(3) + fib(2)
#          fib(3) → fib(2) + fib(1)
#                   fib(2) → fib(1) + fib(0)  ...

🧩 Programmation dynamique

La programmation dynamique évite de recalculer les mêmes sous-problèmes en mémorisant les résultats. Deux approches :

# Fibonacci avec mémoïsation
def fib_memo(n, memo={}):
    if n in memo: return memo[n]
    if n <= 1: return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]
# Complexité : O(n) au lieu de O(2ⁿ) !

# Ou plus élégamment avec le décorateur
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

# Fibonacci avec tabulation
def fib_tab(n):
    if n <= 1: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# Rendu de monnaie (problème classique DP)
def rendu_monnaie(pieces, montant):
    dp = [float('inf')] * (montant + 1)
    dp[0] = 0
    for m in range(1, montant + 1):
        for p in pieces:
            if p <= m:
                dp[m] = min(dp[m], dp[m - p] + 1)
    return dp[montant]

🍽️ Algorithmes gloutons

Un algorithme glouton fait à chaque étape le choix localement optimal, sans revenir en arrière. Simple et rapide, mais ne donne pas toujours la solution globalement optimale.

# Problème du rendu de monnaie (version gloutonne)
def rendu_glouton(pieces, montant):
    # pieces doit être triée par ordre décroissant
    pieces_triees = sorted(pieces, reverse=True)
    resultat = []
    for p in pieces_triees:
        while montant >= p:
            resultat.append(p)
            montant -= p
    return resultat

print(rendu_glouton([1, 2, 5, 10, 20], 36))
# → [20, 10, 5, 1] : 4 pièces — optimal ici !

print(rendu_glouton([1, 3, 4], 6))
# → [4, 1, 1] : 3 pièces — mais [3, 3] c'est mieux !
# L'approche gloutonne échoue ici.

🚨 Pièges classiques au bac

📝 Exercices

def f1(n):                    def f2(lst):
    s = 0                        s = 0
    for i in range(n):              for i in range(len(lst)):
        for j in range(n):              for j in range(i):
            s += 1                      s += lst[j]
    return s                     return s

def f3(n):
    if n <= 0: return 0
    return f3(n // 2) + 1

État initial :  [5, 2, 8, 1, 9, 3]
i=1, clé=2  :  [2, 5, 8, 1, 9, 3]  (2 < 5, on décale 5)
i=2, clé=8  :  [2, 5, 8, 1, 9, 3]  (8 > 5, pas de déplacement)
i=3, clé=1  :  [1, 2, 5, 8, 9, 3]  (1 < 8,5,2, tout décalé)
i=4, clé=9  :  [1, 2, 5, 8, 9, 3]  (9 > 8, pas de déplacement)
i=5, clé=3  :  [1, 2, 3, 5, 8, 9]  (3 entre 2 et 5)
Résultat    :  [1, 2, 3, 5, 8, 9] ✅

def min_pieces(pieces, m):
    dp = [float('inf')] * (m + 1)
    dp[0] = 0
    for montant in range(1, m + 1):
        for p in pieces:
            if p <= montant:
                dp[montant] = ___(dp[montant], ___ + 1)
    return dp[m]

def min_pieces(pieces, m):
    dp = [float('inf')] * (m + 1)
    dp[0] = 0
    for montant in range(1, m + 1):
        for p in pieces:
            if p <= montant:
                dp[montant] = min(dp[montant], dp[montant - p] + 1)
    return dp[m]

print(min_pieces([1,4,6], 8))  # → 2 (4+4)
# L'algorithme glouton donnerait 6+1+1 = 3 pièces → sous-optimal !

📌 Fiche synthèse