1Définition

Face à un énoncé nouveau, la performance ne vient pas de la vitesse de frappe mais d'une méthode : clarifier, chercher le motif connu, écrire une version naïve, mesurer, puis optimiser le vrai goulot. C'est aussi, littéralement, la grille de notation d'un entretien technique.

2Principes fondamentaux

3Exemples pratiques

1# « Existe-t-il deux nombres dont la somme fait la cible ? »2 3# 1. Naïf, O(n²) : toutes les paires4for i in range(len(v)):5    for j in range(i + 1, len(v)):6        if v[i] + v[j] == cible:7            ...8 9# 2. Deux pointeurs, O(n log n) : exige un tri10v = sorted(v)11g, d = 0, len(v) - 112while g < d:13    s = v[g] + v[d]14    if s == cible: break15    elif s < cible: g += 116    else: d -= 117 18# 3. Dictionnaire, O(n) : un seul parcours19vus = set()20for x in v:21    if cible - x in vus:22        ...23    vus.add(x)

1def paire(v, cible):2    vus = set()3    for x in v:4        if cible - x in vus:5            return True6        vus.add(x)7    return False8 9assert paire([10, 25, 75], 100) is True10assert paire([], 100) is False        # liste vide11assert paire([50], 100) is False      # un seul élément12print("Tests OK")

4Erreurs courantes

# taper immédiatement, corriger au fur et à mesure

# reformuler l'énoncé en une phrase, lister les cas limites, puis coder

# raccourcir une boucle de 10 tours dans une fonction appelée une fois

# instrumenter, trouver la boucle réellement coûteuse, l'attaquer

5Subtilités à connaître

• ◆Beaucoup d'énoncés cachent leur contrainte décisive dans une phrase anodine : « la liste est déjà triée » ouvre la dichotomie et les deux pointeurs.
• ◆Quand les mêmes sous-problèmes reviennent, le mot-clé à retenir est programmation dynamique : mémoïsation descendante, ou tableau construit de bas en haut.
• ◆Un algorithme qui tient en mémoire compte autant qu'un algorithme rapide : sur de très grands volumes, on travaille en flux, ligne par ligne.

6Techniques d'expert

import time debut = time.perf_counter()resultat = traiter(donnees)print(round(time.perf_counter() - debut, 4), "s")

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

import random for _ in range(200):    v = [random.randint(0, 50) for _ in range(10)]    assert rapide(v) == naif(v)print("Les deux versions concordent")

7Sur le terrain

• Les entretiens techniques des grandes entreprises évaluent exactement cette méthode : clarification, motif, complexité annoncée, cas limites.
• En production, la plupart des lenteurs viennent d'une recherche répétée dans une liste ou d'une requête dans une boucle — jamais d'un manque de micro-optimisation.
• Les bibliothèques standard sont écrites par des équipes qui ont passé des années sur ces algorithmes : les connaître sert surtout à savoir laquelle appeler.

8Vérifie ta compréhension