Initiation à la complexité algorithmique

Plan de cours

Combien coûte mon algorithme ? La question qui sépare le code qui passe à l'échelle de celui qui plante

Vous savez maintenant écrire des algorithmes. Cette dernière leçon vous apprend à les juger. C'est l'introduction à un domaine immense qui occupe tout un semestre en première année universitaire.

Concepts clés

1. La complexité mesure comment le coût grandit avec la taille N.
2. Classes principales : O(1), O(log N), O(N), O(N log N), O(N²).
3. 1 boucle = O(N) ; 2 boucles imbriquées = O(N²) ; dichotomie = O(log N).
4. L'asymptote domine : O(N²) peut être plus rapide que O(N) pour N petit, mais perd vite.

Avant de commencer

• Q1. Si vous doublez la taille d'un tableau, le temps de recherche séquentielle est-il doublé, multiplié par 4, ou inchangé ?
• Q2. Pourquoi la dichotomie est-elle « presque gratuite » par rapport à la séquentielle ?
• Q3. Connaissez-vous un algorithme dont le temps ne dépend pas du tout de la taille de l'entrée ?

1. Le contenu du cours

1.1 Analogie : la nourriture pour 1 personne ou 100

Préparer un sandwich pour une personne vous prend 2 minutes. Pour deux personnes, ~4 minutes. Pour dix personnes, ~20 minutes. Le temps est proportionnel au nombre de sandwichs : c'est de la complexité linéaire.

Maintenant, trouver un livre sur une étagère de 100 livres rangés alphabétiquement : peu importe qu'il y en ait 100 ou 10 000, vous mettez à peu près le même temps (vous dichotomisez l'étagère). C'est de la complexité logarithmique — quasi-constante.

Enfin, comparer chaque personne avec chaque autre dans une salle de 100 personnes : 100 × 99 = ~10 000 paires. Pour 1000 personnes : 1 000 000 paires. C'est de la complexité quadratique — explosive.

1.2 Définition de la complexité

On utilise la notation grand-O (O majuscule) pour caractériser cette croissance, en ignorant :

• les constantes : O(3N + 5) = O(N),
• les termes dominés : O(N² + N) = O(N²).

1.3 Les cinq classes à connaître

Classe O(1) — Temps constant

Le coût ne dépend pas de N. Exemples :

# Accéder à un élément d'un tableau
def premier_element(T):
    return T[0]   # O(1)

# Tester la parité
def est_pair(n):
    return n % 2 == 0   # O(1)

Classe O(log N) — Temps logarithmique

À chaque étape, on divise par 2 l'espace de travail. Exemples :

# Recherche dichotomique : on divise le tableau par 2
recherche_dicho(T, val)  # O(log N)

# Trouver le nombre de chiffres
def nb_chiffres(n):       # O(log N)
    nb = 0
    while n > 0:
        n = n // 10
        nb += 1
    return nb

Classe O(N) — Temps linéaire

Une seule boucle qui parcourt l'entrée :

def somme(T):              # O(N)
    s = 0
    for x in T:
        s += x
    return s

def maximum(T):            # O(N)
    m = T[0]
    for x in T:
        if x > m:
            m = x
    return m

Classe O(N log N) — Quasi-linéaire

Algorithmes de tri efficaces (hors programme officiel mais culturellement utile). Ce sont les algorithmes les plus rapides théoriquement pour le tri général.

Classe O(N²) — Temps quadratique

Deux boucles imbriquées :

def tri_selection(T):       # O(N²)
    for i in range(len(T)):       # N tours
        for j in range(i, len(T)): # N tours en moyenne
            ...

def comparer_paires(T):     # O(N²)
    for i in range(len(T)):
        for j in range(i + 1, len(T)):
            ...

1.4 Tableau comparatif — N = 10, 100, 1 000, 1 000 000

Observations critiques :

• Pour N = 10, tous les algorithmes sont rapides, même O(N²).
• Pour N = 1 000, O(N²) commence à devenir notable (1 seconde environ).
• Pour N = 1 000 000, O(N²) est impraticable (10¹² opérations = environ plusieurs heures).
• O(log N) est presque gratuit : 20 opérations sur un million d'éléments.

1.5 Identifier la complexité d'un algorithme

Règle empirique : compter les boucles imbriquées (parcours linéaire) et les divisions par 2 (parcours dicho).

Exemple à analyser

def somme_par_paire(T):
    n = len(T)
    total = 0
    for i in range(n):                    # boucle 1 : O(N)
        for j in range(i + 1, n):         # boucle 2 : O(N)
            total += T[i] + T[j]
    return total

→ Deux boucles imbriquées dépendantes : complexité totale O(N²).

def somme_indep(T):
    s1 = 0
    for x in T:           # O(N)
        s1 += x
    
    s2 = 1
    for x in T:           # O(N)
        s2 *= x
    
    return s1 + s2

→ Deux boucles séquentielles : O(N) + O(N) = O(N).

1.6 Comparaisons concrètes

Recherche d'une valeur dans un million d'éléments :

Différence : 25 000 fois plus rapide pour la dichotomie.

Tri d'un million d'éléments :

Le saut O(N²) → O(N log N) est plus important que toute optimisation de constante.

1.7 Cas pratique — Choisir une stratégie

Énoncé. Vous avez un tableau de 100 000 noms et vous voulez :

1. Trier le tableau (une fois).
2. Effectuer 1 000 recherches d'un nom donné dans ce tableau.

Stratégie A — Tout séquentiel

• Tri : pas besoin si on cherche séquentiellement.
• Recherche × 1000 : 1000 × 100000 = 10⁸ opérations.

Stratégie B — Tri puis dichotomie

• Tri (insertion, O(N²)) : 10¹⁰ opérations. Trop coûteux.
• Tri (sélection, O(N²)) : idem.
• Tri (fusion, O(N log N), si vous le connaissez) : 100000 × 17 = 1.7 × 10⁶ opérations.
• Recherche × 1000 dicho : 1000 × 17 = 17 000 opérations.

Total stratégie B : ~1.7 × 10⁶. 60 fois plus rapide que stratégie A.

Conclusion. Pour des données volumineuses avec recherches multiples, trier d'abord est presque toujours rentable — à condition d'utiliser un tri efficace (sorted() Python est O(N log N)).

2. Exercices pratiques

Niveau Débutant — Type bac courant

# Code A
def a(T):
    return T[len(T) // 2]

# Code B
def b(T):
    s = 0
    for x in T:
        s += x
    return s

# Code C
def c(T):
    for i in range(len(T)):
        for j in range(len(T)):
            if T[i] == T[j] and i != j:
                return True
    return False

# Code D
def d(n):
    while n > 1:
        n = n // 2

# Code E
def e(T):
    return T[0] + T[-1]

Niveau Intermédiaire — Type bac difficile

Niveau Avancé — Hors bac (bonus)

def a_doublons_naif(T):
    n = len(T)
    for i in range(n):
        for j in range(i + 1, n):
            if T[i] == T[j]:
                return True
    return False

def a_doublons_tri(T):
    T_trie = sorted(T)            # O(N log N)
    for i in range(len(T_trie) - 1):
        if T_trie[i] == T_trie[i + 1]:
            return True
    return False                   # O(N) pour le parcours

def a_doublons_set(T):
    vus = set()
    for x in T:
        if x in vus:
            return True
        vus.add(x)
    return False

⚠️ Erreurs fréquentes au bac

Avant le quiz, mémorisez ces pièges classiques qui font perdre des points :

• Erreur 1. Confondre O(n) et O(n²) en oubliant les boucles imbriquées. Deux boucles imbriquées sur N = O(N²), pas O(2N).
• Erreur 2. Penser que O(log n) est lent. En réalité, c'est presque constant : pour N = 10⁹, log₂(N) ≈ 30.
• Erreur 3. Ignorer les constantes pour les petits n. 10n est plus lent que n² si n < 10. La complexité asymptotique compte pour les grands n.
• Erreur 4. Mettre une opération coûteuse (comme len(T)) dans la condition d'une boucle : recalculée à chaque tour. Stocker dans une variable.

3. Quiz de vérification

En résumé — Fin du programme officiel

Bravo. Vous avez parcouru les 4 chapitres du programme officiel de 4ème année :

• ✅ Chapitre 1 — Structures de contrôle I (rappels, conditionnelles, itératives complètes, fonctions prédéfinies).
• ✅ Chapitre 2 — Structures de contrôle II (Répéter, Tant que, choix de structure).
• ✅ Chapitre 3 — Sous-programmes (analyse modulaire, procédures/fonctions, paramètres, tableaux, chaînes).
• ✅ Chapitre 4 — Traitements avancés (recherche, tri, complexité).

Compétences acquises :

• Lire un énoncé et produire le triptyque Analyse → Algorithme → Python.
• Choisir les bonnes structures de contrôle et de données.
• Découper un problème en sous-programmes cohérents et testables.
• Estimer la complexité d'un algorithme et choisir entre plusieurs solutions.

Étape suivante : l'examen final blanc. Une épreuve de 2 heures, composée d'une partie théorique (45 min, 8 points) et d'une étude de cas pratique (75 min, 12 points). Allez sur /examens/bac-blanc-final-2h quand vous vous sentez prêt(e). Une grille de correction détaillée vous permettra de vous auto-évaluer.

Bon courage pour vos prochaines révisions et pour le bac.