Méthodes & Algorithmes

📊 Tableau des complexités

Notation	Nom	Exemple	n=1000
O(1)	Constante	Accès dict, accès liste[i]	1 op
O(log n)	Logarithmique	Recherche dichotomique	~10 op
O(n)	Linéaire	Parcours liste	1 000 op
O(n log n)	Quasi-linéaire	Tri fusion, tri rapide moy.	~10 000 op
O(n²)	Quadratique	Tri à bulles, sélection	1 000 000 op
O(2ⁿ)	Exponentielle	Fibonacci naïf	10³⁰⁰ op !
O(n!)	Factorielle	Permutations	Impossible

🔀 Algorithmes de tri

Tri à bulles — O(n²)

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

Principe : Compare paires adjacentes, fait "remonter" les grands éléments. Stable. O(n²) toujours.

Tri par sélection — O(n²)

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

Principe : Cherche le minimum du sous-tableau non trié et le place en position i. N échanges max. Non stable.

Tri par insertion — O(n²)

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

Principe : Insère chaque élément à sa place dans la partie déjà triée. Stable. Efficace si presque trié : O(n).

Tri fusion — O(n log n) garanti

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:]

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

Principe : Divise le tableau en deux, trie chaque moitié récursivement, fusionne. Stable. O(n log n) toujours ✓

Algorithme	Meilleur	Moyen	Pire	Stable
Bulles	O(n)	O(n²)	O(n²)	Oui
Sélection	O(n²)	O(n²)	O(n²)	Non
Insertion	O(n)	O(n²)	O(n²)	Oui
Fusion	O(n log n)	O(n log n)	O(n log n)	Oui
Rapide	O(n log n)	O(n log n)	O(n²)	Non

🔍 Algorithmes de recherche

Recherche dichotomique — O(log n)

⚠️

Prérequis absolu

Le tableau doit être trié pour que la recherche dichotomique fonctionne !

def recherche_dicho(tab, cible):
    # Version itérative — à préférer au bac
    gauche, droite = 0, len(tab) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if tab[milieu] == cible:
            return milieu        # trouvé à l'indice milieu
        elif tab[milieu] < cible:
            gauche = milieu + 1   # chercher à droite
        else:
            droite = milieu - 1   # chercher à gauche
    return -1                   # non trouvé

🔄 Récursion

✅ Structure d'une fonction récursive

Un cas de base (condition d'arrêt) — obligatoire !
Un appel récursif sur un problème plus petit
La garantie que le cas de base est atteint

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

# Fibonacci avec mémoïsation
def fib(n, memo={}):
    if n <= 1: return n
    if n not in memo:
        memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

🕸️ Parcours de graphes

BFS — Parcours en largeur

from collections import deque

def bfs(graphe, depart):
    visites = {depart}
    file = deque([depart])
    ordre = []
    while file:
        sommet = file.popleft()
        ordre.append(sommet)
        for voisin in graphe[sommet]:
            if voisin not in visites:
                visites.add(voisin)
                file.append(voisin)
    return ordre

Utilise une file. Trouve le plus court chemin (non pondéré). O(V + E).

DFS — Parcours en profondeur

def dfs(graphe, sommet, visites=None):
    if visites is None: visites = set()
    visites.add(sommet)
    print(sommet)
    for voisin in graphe[sommet]:
        if voisin not in visites:
            dfs(graphe, voisin, visites)
    return visites

Utilise la récursion (ou une pile). Explore le plus loin possible avant de revenir. O(V + E).

Dijkstra — Plus courts chemins

import heapq

def dijkstra(graphe, depart):
    # graphe[s] = [(voisin, poids), ...]
    dist = {s: float('inf') for s in graphe}
    dist[depart] = 0
    tas = [(0, depart)]  # (distance, sommet)
    while tas:
        d, u = heapq.heappop(tas)
        if d > dist[u]: continue
        for v, poids in graphe[u]:
            nd = dist[u] + poids
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(tas, (nd, v))
    return dist

Poids positifs uniquement. O((V + E) log V) avec un tas binaire.

🗄️ SQL — Aide-mémoire

-- Structure générale d'une requête SQL
SELECT colonne1, COUNT(*) AS nb
FROM table1
JOIN table2 ON table1.id = table2.fk_id
WHERE condition
GROUP BY colonne1
HAVING COUNT(*) > 1
ORDER BY colonne1 DESC
LIMIT 10;

🚨

Ordre d'exécution SQL (pas l'ordre d'écriture !)

FROM → JOIN → WHERE → GROUP BY → HAVING → SELECT → ORDER BY → LIMIT

C'est pourquoi on ne peut pas utiliser un alias du SELECT dans le WHERE.

Clause	Rôle
WHERE	Filtre les lignes avant GROUP BY
GROUP BY	Regroupe les lignes par valeur
HAVING	Filtre les groupes (après GROUP BY)
JOIN	Jointure entre deux tables sur une condition
LEFT JOIN	Garde toutes les lignes de gauche, NULL si pas de correspondance
COUNT(*)	Nombre de lignes dans le groupe
COUNT(col)	Nombre de valeurs non NULL

🐍 Python — Astuces essentielles

# Compréhensions de liste
carres = [x**2 for x in range(10) if x % 2 == 0]

# Décompression / échange
a, b = b, a   # swap en Python sans variable tmp
a, *reste = [1, 2, 3, 4]  # a=1, reste=[2,3,4]

# Dictionnaire par défaut
from collections import defaultdict
d = defaultdict(list)
d['cle'].append(1)  # pas de KeyError

# Trier avec clé personnalisée
sorted(liste, key=lambda x: x[1], reverse=True)

# Stack / Queue
from collections import deque
file = deque()
file.append(1)     # enfiler
file.popleft()    # défiler O(1)

# Récursion + mémoïsation
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
    if n < 2: return n
    return fib(n-1) + fib(n-2)