Algorithmique & Python avancé

Algorithmique & Python avancé

Cette fiche est délibérément hors programme lycée. On y aborde des notions que tu retrouveras en spécialité NSI, en classe préparatoire ou en première année post-bac : complexité algorithmique, structures de données efficaces, idiomes Pythoniques, récursivité et bonnes pratiques d'ingénieur logiciel.

À la fin, tu sauras estimer le coût d'un algorithme avec la notation $O(n)$, choisir entre une liste et un dictionnaire selon le besoin, écrire des compréhensions de listes et de dictionnaires, accélérer une fonction récursive avec la mémoïsation, et structurer du code propre avec des dataclass et des assert.

Complexité algorithmique : $O(1)$, $O(n)$, $O(\log n)$

La complexité d'un algorithme décrit comment son temps d'exécution évolue quand la taille des données augmente. On la note avec un grand O. Trois ordres de grandeur reviennent sans cesse :

• $O(1)$ — temps constant : accéder à liste[i], lire une variable.
• $O(n)$ — temps linéaire : parcourir une liste de n éléments.
• $O(\log n)$ — temps logarithmique : recherche dichotomique dans une liste triée.

Comparons une recherche linéaire et une recherche dichotomique :

Les deux trouvent la cible. Mais sur une liste d'un million d'éléments, la dichotomique fait au plus une vingtaine d'itérations contre presque un million pour la linéaire ($\log_2(10^6) \approx 20$).

On peut mesurer concrètement avec time.perf_counter :

import math
n = 1024
reponse = int(math.log2(n))
print(reponse)

def somme_paires(L):
    total = 0
    for x in L:
        if x % 2 == 0:
            total += x
    return total

print(somme_paires([1, 2, 3, 4, 5, 6]))

Dictionnaires et tables de hachage

Le dictionnaire (dict) est la structure phare de Python : il associe une clé à une valeur et permet l'accès en $O(1)$ moyen, grâce à une table de hachage. C'est radicalement plus rapide qu'une recherche dans une liste.

Cas d'usage emblématique : compter les occurrences. Avec une liste, il faudrait L.count(x) pour chaque x distinct, soit $O(n^2)$. Avec un dict, on fait un seul passage en $O(n)$ :

Encore plus idiomatique : collections.Counter fait exactement la même chose, en plus court :

notes = {'Léa': 14, 'Tom': 11, 'Inès': 17}
print(notes.get('Inès'))
print(notes.get('Zoé'))

notes = {'Léa': 14, 'Tom': 11}
print('Tom' in notes)

from collections import Counter

def anagramme(a, b):
    return Counter(a) == Counter(b)

print(anagramme('chien', 'niche'))
print(anagramme('python', 'java'))

Compréhensions et idiomes Pythoniques

Une compréhension construit une liste, un dict ou un set en une expression. C'est la forme la plus idiomatique d'écrire une boucle qui filtre/transforme. Trois familles :

On peut filtrer (if) et transformer (expr avant le for) en même temps. C'est plus lisible — et souvent plus rapide — qu'une boucle for explicite avec append.

zip et enumerate sont des compagnons indispensables :

cubes = [n ** 3 for n in range(1, 6)]
print(cubes)

mots = ['python', 'algorithme', 'liste', 'dict']
longueurs = {m: len(m) for m in mots}
print(longueurs)

multiples = [n for n in range(1, 31) if n % 3 == 0 or n % 5 == 0]
print(multiples)
print(sum(multiples))

Récursivité et mémoïsation

Une fonction récursive s'appelle elle-même avec un argument plus petit, jusqu'à atteindre un cas de base. Exemple classique : la suite de Fibonacci définie par $F_0 = 0$, $F_1 = 1$, $F_n = F_{n-1} + F_{n-2}$.

Le code est élégant, mais exponentiel : fib(40) fait des milliards d'appels redondants. Solution : mémoriser les résultats déjà calculés. C'est la mémoïsation, offerte par functools.lru_cache en un décorateur :

Avec le cache, la complexité passe de $O(\varphi^n)$ à $O(n)$ — fib_memo(100) est instantané et donne un entier de 21 chiffres (rappel : Python gère les grands entiers nativement).

Attention au plafond de récursion : Python l'arrête vers 1000 appels imbriqués pour éviter de faire planter la pile. On peut lire ou changer la limite :

def factorielle_iter(n):
    resultat = 1
    for k in range(2, n + 1):
        resultat *= k
    return resultat

print(factorielle_iter(20))

Code propre : dataclasses, type hints, tests

Quand un programme grossit, on manipule des objets structurés plutôt que des tuples ou des dicts. Le décorateur @dataclass génère automatiquement __init__, __repr__ et __eq__ :

Les annotations x: float sont des type hints : Python ne les vérifie pas à l'exécution, mais elles documentent l'intention et sont exploitées par des outils comme mypy ou les IDE.

Pour vérifier qu'une fonction se comporte comme attendu, on écrit des tests. La forme la plus simple : assert, qui lève une erreur si la condition est fausse.

Si l'un des assert échoue, Python affiche une AssertionError avec la ligne fautive. C'est le b.a.-ba du TDD (Test-Driven Development).

from dataclasses import dataclass

@dataclass
class Vecteur:
    x: float
    y: float

v = Vecteur(2, -1)
print(v)

from dataclasses import dataclass

@dataclass
class Vecteur:
    x: float
    y: float

assert Vecteur(1, 2) == Vecteur(1, 2)
print('OK')

from dataclasses import dataclass

@dataclass
class Élève:
    nom: str
    notes: list

    def moyenne(self):
        return sum(self.notes) / len(self.notes)

e = Élève('Léa', [12, 16, 14])
assert e.moyenne() == 14
assert Élève('Tom', [10, 10]).moyenne() == 10
print('Tests OK')

def premiers(n):
    for k in range(2, n):
        if all(k % d != 0 for d in range(2, int(k ** 0.5) + 1)):
            yield k

print(list(premiers(50)))