Algorithmique — Complexité et algorithmes fondamentaux

1. Notion de complexité

La complexité mesure l’efficacité d’un algorithme en fonction de la taille des données. On distingue :

• Complexité temporelle : temps d’exécution (ex: O(n) pour une boucle simple).
• Complexité spatiale : mémoire utilisée (ex: O(1) pour une variable).

Exemple : Un tri par sélection a une complexité O(n²) car il compare chaque élément à tous les autres.

2. Notations asymptotiques

On utilise les notations Big O pour simplifier l’analyse :

• O(1) : temps constant (ex: accès à un tableau).
• O(log n) : temps logarithmique (ex: recherche dichotomique).
• O(n) : temps linéaire (ex: parcours d’une liste).
• O(n²) : temps quadratique (ex: tri bulle).

Règle : On garde le terme dominant (ex: O(n² + n) devient O(n²)).

3. Algorithmes fondamentaux

a. Recherche linéaire

Parcours séquentiel d’une liste. Complexité : O(n).

def recherche_lineaire(liste, x):
    for i in range(len(liste)):
        if liste[i] == x:
            return i
    return -1

b. Recherche dichotomique

Nécessite une liste triée. Complexité : O(log n).

def recherche_dichotomique(liste, x):
    gauche, droite = 0, len(liste)-1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if liste[milieu] == x:
            return milieu
        elif liste[milieu] < x:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1

c. Tri par sélection

Trouve le minimum à chaque itération. Complexité : O(n²).

def tri_selection(liste):
    for i in range(len(liste)):
        min_idx = i
        for j in range(i+1, len(liste)):
            if liste[j] < liste[min_idx]:
                min_idx = j
        liste[i], liste[min_idx] = liste[min_idx], liste[i]

4. Choix de l’algorithme

• Petites données : Un algorithme simple (ex: tri bulle) peut suffire.
• Grandes données : Privilégier des algorithmes efficaces (ex: tri rapide O(n log n)).

Exemple : Pour trier 1 million d’éléments, un O(n²) sera lent, un O(n log n) sera optimal.

5. Optimisation

• Éviter les boucles imbriquées : Réduire la complexité (ex: passer de O(n²) à O(n)).
• Utiliser des structures adaptées : Dictionnaires pour des recherches rapides (O(1)).

Cas pratique : Stocker des données dans un dictionnaire pour des accès instantanés.