Structures de données & Algorithmes

01 — Complexité

Notation Big O

La notation Big O décrit comment le temps d'exécution (ou la mémoire) d'un algorithme évolue en fonction de la taille de l'entrée n. On analyse toujours le pire cas.

O(1) — Constant

dict[key], list[-1]

Indépendant de n. Le meilleur cas possible.

O(log n) — Logarithmique

Recherche binaire

Double n → +1 étape seulement.

O(n) — Linéaire

Parcours de liste, in list

Proportionnel à n. Acceptable.

O(n log n)

sorted(), merge sort

Tris efficaces. Quasi-optimal pour le tri.

O(n²) — Quadratique

Boucle dans boucle

Lent pour grands n. À éviter.

O(2ⁿ) — Exponentiel

Fibonacci naïf, sous-ensembles

Impraticable au-delà de n≈30.

💡

Règle pratique : on ignore les constantes et termes dominés. O(3n + 5) → O(n). O(n² + n) → O(n²).

01b — Complexité

Complexités des structures Python

Structure	Accès	Recherche	Insertion	Suppression
list	O(1)	O(n)	O(1) fin / O(n) début	O(1) fin / O(n) début
dict	O(1) moy.	O(1) moy.	O(1) moy.	O(1) moy.
set	—	O(1) moy.	O(1) moy.	O(1) moy.
deque	O(n)	O(n)	O(1) tête/queue	O(1) tête/queue
heapq	—	—	O(log n)	O(log n)
sorted list	O(1)	O(log n)	O(n)	O(n)

02 — Structures intégrées

Listes

Tableaux dynamiques ordonnés et mutables. Structure la plus polyvalente de Python.

Python

# Création
lst = [1, 2, 3, 4, 5]
lst = list(range(10))

# Opérations clés
lst.append(6)      # O(1) — fin
lst.insert(0, 0)   # O(n) — début !
lst.pop()          # O(1) — fin
lst.pop(0)         # O(n) — début !
3 in lst            # O(n) — recherche linéaire

# Slicing
lst[1:4]            # [2, 3, 4]
lst[::-1]           # inversé

# Compréhension de liste
carrés = [x**2 for x in lst if x % 2 == 0]

# Trier
lst.sort()                   # en place, O(n log n)
sorted(lst, reverse=True)  # nouvelle liste

⚠️

Piège fréquent : insert(0, x) et pop(0) sont O(n) car tous les éléments se décalent. Utiliser collections.deque si vous avez besoin d'opérations fréquentes en tête de liste.

Quand utiliser une liste ?

Collection ordonnée avec accès par index

Ajouts et retraits principalement en fin

Itération séquentielle fréquente

Éléments dupliqués autorisés

02b

Dictionnaires

Tables de hachage clé→valeur. Accès, insertion, suppression en O(1) moyen. Ordonnés depuis Python 3.7.

Python

# Création
d = {"nom": "Alice", "age": 23}
d = dict(nom="Alice", age=23)

# Accès sécurisé
d["nom"]              # KeyError si absent
d.get("email", "")    # "" si absent

# Modification
d["ville"] = "MTL"   # O(1)
del d["age"]           # O(1)

# Itération
for k, v in d.items():
    print(k, v)

# setdefault / defaultdict
from collections import defaultdict
freq = defaultdict(int)
for mot in texte:
    freq[mot] += 1   # jamais de KeyError

# Compréhension
carré = {x: x**2 for x in range(5)}

💡

Les clés doivent être hashables (immutables) : str, int, tuple. Les listes ne peuvent pas être clés.

Comptage de fréquences — pattern classique :

Python

from collections import Counter
mots = ["a", "b", "a", "c", "a"]
c = Counter(mots)
# Counter({'a': 3, 'b': 1, 'c': 1})
c.most_common(2)
# [('a', 3), ('b', 1)]

02c

Sets & Tuples

Sets — ensembles non ordonnés uniques

Python

s = {1, 2, 3, 2}   # {1, 2, 3}
s.add(4)            # O(1)
3 in s              # O(1) ← gros avantage vs liste

# Opérations ensemblistes
a | b   # union
a & b   # intersection
a - b   # différence
a ^ b   # différence symétrique

# Dédoublonner une liste
unique = list(set(ma_liste))

Tuples — listes immuables

Python

t = (1, 2, 3)
x, y, z = t         # déstructuration

# namedtuple — lisibilité
from collections import namedtuple
Point = namedtuple('Point', ['x', 'y'])
p = Point(3, 4)
p.x, p.y            # accès par nom

# Utilisations typiques
# - clé de dictionnaire
# - retour multiple de fonction
# - données constantes

💡

Utiliser un set plutôt qu'une liste pour les recherches fréquentes : x in set est O(1) vs O(n) pour une liste.

03 — Structures avancées

Piles & Files

🥞 Pile (Stack) — LIFO

Last In, First Out. Dernier entré, premier sorti. Utiliser une list Python.

Python

pile = []
pile.append("a")   # push — O(1)
pile.append("b")
pile.append("c")
pile.pop()         # pop → "c" — O(1)
pile[-1]           # peek → "b" — O(1)

# Usages : undo/redo, appels récursifs,
# parsing d'expressions, DFS

🚶 File (Queue) — FIFO

First In, First Out. Utiliser collections.deque pour O(1) des deux côtés.

Python

from collections import deque

file = deque()
file.append("a")      # enqueue — O(1)
file.append("b")
file.popleft()         # dequeue → "a" — O(1)

# File de priorité (tas)
import heapq
tas = []
heapq.heappush(tas, (2, "b"))
heapq.heappush(tas, (1, "a"))
heapq.heappop(tas)     # (1, "a")

⚠️

Ne jamais faire list.pop(0) comme file — c'est O(n). Toujours utiliser deque.popleft().

03b

Arbres

Structure hiérarchique. Un nœud racine, des enfants, des feuilles. Traversée en O(n).

Python

class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur
        self.gauche = None
        self.droite = None

# Arbre binaire de recherche (BST)
# Invariant : gauche < nœud < droite
def inserer(racine, val):
    if racine is None:
        return Noeud(val)
    if val < racine.valeur:
        racine.gauche = inserer(racine.gauche, val)
    else:
        racine.droite = inserer(racine.droite, val)
    return racine

# Parcours en ordre (donne les valeurs triées)
def inordre(noeud):
    if noeud:
        inordre(noeud.gauche)
        print(noeud.valeur)
        inordre(noeud.droite)

3 types de parcours

Parcours	Ordre	Usage typique
Préordre	Racine → G → D	Copier un arbre
Inordre	G → Racine → D	Valeurs triées (BST)
Postordre	G → D → Racine	Supprimer un arbre

ℹ️

BST équilibré : recherche O(log n). BST dégénéré (valeurs triées à l'insertion) : O(n). Python n'a pas de BST intégré — utiliser sortedcontainers.SortedList si besoin.

03c

Graphes

Ensemble de nœuds (sommets) reliés par des arêtes. Peut être orienté ou non, pondéré ou non.

Python — Liste d'adjacence

# Représentation standard
graphe = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"],
}

# BFS — exploration en largeur (file)
from collections import deque
def bfs(graphe, depart):
    visités = set()
    file = deque([depart])
    while file:
        nœud = file.popleft()
        if nœud not in visités:
            visités.add(nœud)
            file.extend(graphe[nœud])
    return visités

# DFS — exploration en profondeur (pile/récursion)
def dfs(graphe, nœud, visités=None):
    if visités is None: visités = set()
    visités.add(nœud)
    for voisin in graphe[nœud]:
        if voisin not in visités:
            dfs(graphe, voisin, visités)
    return visités

Algo	Complexité	Usage
BFS	O(V+E)	Plus court chemin (non pondéré)
DFS	O(V+E)	Cycle, composantes connexes
Dijkstra	O((V+E)log V)	Plus court chemin pondéré

ℹ️

V = nombre de sommets, E = nombre d'arêtes. BFS garantit le chemin le plus court en nombre d'arêtes. DFS consomme moins de mémoire.

04 — Algorithmes

Algorithmes de tri

Tri à bulles (Bubble Sort)

Ω(n) θ(n²) O(n²)

Compare et échange les paires adjacentes. Simple mais inefficace. Valeur pédagogique uniquement.

Python

def tri_bulles(lst):
    n = len(lst)
    for i in range(n):
        for j in range(0, n - i - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]

Tri par insertion (Insertion Sort)

Ω(n) θ(n²) O(n²)

Insère chaque élément à sa place dans la partie déjà triée. Efficace sur les petites listes ou presque triées.

Python

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

Tri fusion (Merge Sort)

Ω(n log n) θ(n log n) O(n log n)

Diviser pour régner : sépare en deux moitiés, trie chacune récursivement, fusionne. Stable et prévisible. Coût mémoire : O(n).

Python

def tri_fusion(lst):
    if len(lst) <= 1:
        return lst
    mid = len(lst) // 2
    G = tri_fusion(lst[:mid])
    D = tri_fusion(lst[mid:])
    return fusionner(G, D)

def fusionner(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:]

💡

En pratique, toujours utiliser sorted() ou .sort() — Python utilise Timsort, un hybride merge sort + insertion sort en O(n log n) avec optimisations. Ne jamais réimplémenter le tri en production.

04b

Recherche

Recherche linéaire — O(n)

Python

# Intégré — utiliser directement
if 42 in ma_liste:     # O(n)
    ...
idx = ma_liste.index(42)  # O(n)

# Implémentation manuelle (pédagogique)
def recherche_lineaire(lst, cible):
    for i, val in enumerate(lst):
        if val == cible:
            return i
    return -1

Recherche binaire — O(log n)

Nécessite une liste triée. Divise l'espace de recherche par deux à chaque étape.

Python

# Module intégré (préférer)
import bisect
lst = [1, 3, 5, 7, 9]
bisect.bisect_left(lst, 5)   # → 2

# Implémentation manuelle
def recherche_binaire(lst, cible):
    g, d = 0, len(lst) - 1
    while g <= d:
        mid = (g + d) // 2
        if   lst[mid] == cible: return mid
        elif lst[mid] <  cible: g = mid + 1
        else:                   d = mid - 1
    return -1

04c

Récursion

Une fonction qui s'appelle elle-même. Toujours deux parties : le cas de base (arrêt) et le cas récursif (réduction).

Python — Exemples classiques

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

# Fibonacci naïf — O(2ⁿ) !
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

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

# Puissance rapide — O(log n)
def puissance(base, exp):
    if exp == 0: return 1
    if exp % 2 == 0:
        mid = puissance(base, exp // 2)
        return mid * mid
    return base * puissance(base, exp - 1)

⚠️

Python limite la récursion à ~1000 appels par défaut (sys.setrecursionlimit). Pour les grandes profondeurs, convertir en version itérative avec une pile explicite.

Règle des 3 questions (avant d'écrire)

1. Quel est le cas de base ? (quand s'arrête-t-on ?)
2. Comment réduire le problème vers le cas de base ?
3. La récursion fait-elle des calculs redondants ? (→ mémoïsation)

💡

Mémoïsation : stocker les résultats déjà calculés pour éviter les doublons. @lru_cache le fait automatiquement. Transforme O(2ⁿ) en O(n).

04b — Structures avancées

Tables de hachage — implémentation interne

Un dict Python est une table de hachage. Comprendre son mécanisme interne explique pourquoi la recherche est O(1) — et quand elle peut déraper vers O(n).

Implémentation minimaliste d'une table de hachage

class TableHachage:
    def __init__(self, capacite=16):
        self.capacite = capacite
        self.buckets = [[] for _ in range(capacite)]
        self.taille = 0

    def _indice(self, cle):
        return hash(cle) % self.capacite   # compartiment

    def set(self, cle, valeur):
        idx = self._indice(cle)
        for i, (k, v) in enumerate(self.buckets[idx]):
            if k == cle:                   # mettre à jour
                self.buckets[idx][i] = (cle, valeur)
                return
        self.buckets[idx].append((cle, valeur))  # insérer
        self.taille += 1
        if self.taille / self.capacite > 0.75:  # facteur de charge
            self._redimensionner()

    def get(self, cle, defaut=None):
        idx = self._indice(cle)
        for k, v in self.buckets[idx]:
            if k == cle: return v
        return defaut

    def _redimensionner(self):
        # Doubler la capacité, ré-hacher tout
        anciens = self.buckets
        self.capacite *= 2
        self.buckets = [[] for _ in range(self.capacite)]
        self.taille = 0
        for bucket in anciens:
            for k, v in bucket:
                self.set(k, v)

t = TableHachage()
t.set('alice', 20)
t.set('bob', 25)
print(t.get('alice'))  # 20

⚙️

Collision : deux clés différentes donnent le même index (hash(cle) % capacite). La stratégie ici est le chaînage séparé — chaque bucket est une liste. L'autre stratégie courante est l'adressage ouvert (le dict Python l'utilise).

Opération	Cas moyen	Pire cas	Condition pire cas
Insertion	O(1)	O(n)	Toutes les clés dans le même bucket
Recherche	O(1)	O(n)	Même — ou mauvaise fonction de hachage
Suppression	O(1)	O(n)	Idem
Redimensionnement	O(n)	O(n)	Amortized O(1) sur n insertions

Pièges et bonnes pratiques avec dict Python

# ✓ Clés hashables : str, int, tuple, frozenset
d = {(1, 2): 'point'}   # tuple = hashable

# ✗ Clés non hashables : list, dict, set
# d = {[1,2]: 'erreur'}  → TypeError !

# Compter les occurrences — pattern classique
from collections import Counter, defaultdict

mots = "le chat et le chien".split()
freq = Counter(mots)          # {'le': 2, 'chat': 1, ...}
print(freq.most_common(2))   # [('le', 2), ('chat', 1)]

# defaultdict — éviter les KeyError
graphe = defaultdict(list)
graphe['A'].append('B')     # pas besoin de vérifier si 'A' existe

# setdefault — initialiser si absent
d = {}
d.setdefault('cle', []).append(1)

04c

Arbres binaires de recherche (BST)

Un BST est un arbre binaire où pour chaque nœud : tous les éléments du sous-arbre gauche sont inférieurs, tous ceux du sous-arbre droit sont supérieurs. Cela rend la recherche O(log n) — si l'arbre est équilibré.

Implémentation complète d'un BST

class Noeud:
    def __init__(self, valeur):
        self.val    = valeur
        self.gauche = None
        self.droite = None

class BST:
    def __init__(self):
        self.racine = None

    def inserer(self, valeur):
        self.racine = self._inserer(self.racine, valeur)

    def _inserer(self, noeud, valeur):
        if not noeud: return Noeud(valeur)
        if   valeur < noeud.val: noeud.gauche = self._inserer(noeud.gauche, valeur)
        elif valeur > noeud.val: noeud.droite = self._inserer(noeud.droite, valeur)
        return noeud

    def rechercher(self, valeur):
        return self._rechercher(self.racine, valeur)

    def _rechercher(self, noeud, valeur):
        if not noeud: return False
        if   valeur == noeud.val: return True
        elif valeur <  noeud.val: return self._rechercher(noeud.gauche, valeur)
        else:                     return self._rechercher(noeud.droite, valeur)

    def infixe(self):
        "Parcours infixe = éléments dans l'ordre croissant"
        resultat = []
        def parcourir(n):
            if not n: return
            parcourir(n.gauche)
            resultat.append(n.val)
            parcourir(n.droite)
        parcourir(self.racine)
        return resultat

    def supprimer(self, valeur):
        self.racine = self._supprimer(self.racine, valeur)

    def _supprimer(self, noeud, valeur):
        if not noeud: return None
        if   valeur < noeud.val: noeud.gauche = self._supprimer(noeud.gauche, valeur)
        elif valeur > noeud.val: noeud.droite = self._supprimer(noeud.droite, valeur)
        else:                          # noeud trouvé
            if not noeud.gauche: return noeud.droite
            if not noeud.droite: return noeud.gauche
            # 2 enfants : remplacer par le successeur (min du sous-arbre droit)
            successeur = noeud.droite
            while successeur.gauche: successeur = successeur.gauche
            noeud.val = successeur.val
            noeud.droite = self._supprimer(noeud.droite, successeur.val)
        return noeud

bst = BST()
for v in [5, 3, 7, 1, 4, 6, 8]: bst.inserer(v)
print(bst.infixe())       # [1, 3, 4, 5, 6, 7, 8]
print(bst.rechercher(4))  # True

BST avec [5,3,7,1,4,6,8]
5
/ \
3 7
/ \ / \
1 4 6 8

Infixe (G-R-D) : 1 3 4 5 6 7 8 ← trié !
Préfixe (R-G-D) : 5 3 1 4 7 6 8
Suffixe (G-D-R) : 1 4 3 6 8 7 5

Opération	Équilibré	Dégénéré*
Recherche	O(log n)	O(n)
Insertion	O(log n)	O(n)
Suppression	O(log n)	O(n)
Min / Max	O(log n)	O(n)
Parcours infixe	O(n)	O(n)

⚠️

* Un BST inséré en ordre trié [1,2,3,4,5] dégénère en une liste chaînée — toutes les opérations deviennent O(n). En pratique, utiliser des arbres auto-équilibrés comme AVL ou Red-Black Tree. Python n'en fournit pas nativement — préférer sortedcontainers.SortedList.

04d — Visualisations

Animations — voir les algorithmes en action

Visualiser ce qui se passe à chaque étape est la façon la plus rapide de comprendre un algorithme. Voici des simulateurs interactifs pour les tris simples.

Algorithme :

Comparaisons : 0 Échanges : 0 Étape : — Vitesse :

🎨

Légende des couleurs : ■ Violet = tableau de base — ■ Jaune = éléments en cours de comparaison — ■ Rouge = pivot ou minimum — ■ Vert = élément positionné définitivement.

💡

Observe comment le tri à bulles fait de nombreux échanges, l'insertion ne déplace que ce qui est nécessaire, et le merge sort divise avant de fusionner — ce qui explique ses meilleures performances.

05b — Exercices

Exercices — choisir la bonne structure

Quatre problèmes où le choix de la structure de données est la clé de la solution efficace.

📚 File de priorité — salle d'attente

O(log n)

Gérer des patients par ordre de priorité (urgence). Toujours traiter le plus urgent en premier.

heapq — min-heap Python

import heapq

# Tuple (priorité, nom) — trie par priorité croissante
# Astuce : priorité négative pour avoir le plus grand d'abord
salle = []
heapq.heappush(salle, (3, 'Bob'))     # faible urgence
heapq.heappush(salle, (1, 'Alice'))   # critique
heapq.heappush(salle, (2, 'Charlie')) # modéré

while salle:
    prio, nom = heapq.heappop(salle)  # O(log n)
    print(f"Traiter : {nom} (urgence {prio})")
# Alice (1), Charlie (2), Bob (3)

🔁 Palindrome avec pile

O(n)

Vérifier un palindrome

def est_palindrome(mot):
    pile = list(mot)
    reconstitue = ''
    while pile:
        reconstitue += pile.pop()   # pile → ordre inversé
    return mot == reconstitue

# Version plus simple
def palindrome_v2(mot): return mot == mot[::-1]

print(est_palindrome('radar'))   # True
print(est_palindrome('python'))  # False

⚖️ Parenthèses équilibrées

O(n)

Vérifier que ({[]}) est bien fermé dans le bon ordre. Classique d'examen et d'entretien.

Pile pour les parenthèses

def parentheses_valides(s):
    pile = []
    ferme = {')':'(', ']':'[', '}':'{'}
    for c in s:
        if c in '([{':
            pile.append(c)
        elif c in ferme:
            if not pile or pile[-1] != ferme[c]:
                return False
            pile.pop()
    return not pile  # pile vide = tout fermé

print(parentheses_valides("({[]})"))   # True
print(parentheses_valides("([)]"))     # False

🌊 BFS — niveau par niveau

O(V+E)

Parcours niveau par niveau (arbre ou graphe)

from collections import deque

def bfs_niveaux(racine, voisins):
    niveaux = []
    file = deque([(racine, 0)])
    vus = {racine}
    while file:
        noeud, lvl = file.popleft()
        if lvl == len(niveaux):
            niveaux.append([])
        niveaux[lvl].append(noeud)
        for v in voisins.get(noeud, []):
            if v not in vus:
                vus.add(v); file.append((v, lvl+1))
    return niveaux
# Utile pour : distance minimale, arbre de mots,
# connexions sociales, labyrinthe

05 — Référence

Cheat sheet

Choisir une structure

Séquence ordonnée	list
Clé → Valeur	dict
Unicité, recherche rapide	set
Immuable	tuple
File / Pile efficace	deque
File de priorité	heapq

Complexités clés

dict/set lookup	O(1)
list[i]	O(1)
Recherche binaire	O(log n)
sorted() / .sort()	O(n log n)
list.insert(0,x)	O(n)
x in list	O(n)

Tris — résumé

Bulles	O(n²)
Insertion	O(n²)
Fusion	O(n log n)
Timsort (Python)	O(n log n)
Recherche linéaire	O(n)
Recherche binaire	O(log n)

Organiser& Résoudre

Notation Big O

Complexités des structures Python

Listes

Dictionnaires

Sets & Tuples

Piles & Files

Arbres

Graphes

Algorithmes de tri

Tri à bulles (Bubble Sort)

Tri par insertion (Insertion Sort)

Tri fusion (Merge Sort)

Recherche

Récursion

Règle des 3 questions (avant d'écrire)

Tables de hachage — implémentation interne

Arbres binaires de recherche (BST)

Animations — voir les algorithmes en action

Exercices — choisir la bonne structure

📚 File de priorité — salle d'attente

🔁 Palindrome avec pile

⚖️ Parenthèses équilibrées

🌊 BFS — niveau par niveau

Cheat sheet

Choisir une structure

Complexités clés

Tris — résumé

Organiser
& Résoudre