Comment évaluer la complexité d'un algorithme ou…

Pour évaluer la complexité d'un algorithme, on utilise l'analyse asymptotique, qui permet de décrire l'efficacité de l'algorithme en fonction de la taille des données d'entrée ($n$). Les étapes principales:

Définition des opérations de base: On identifie les opérations dont le temps d'exécution dépend significativement de $n$ (par exemple, comparaisons, affectations, opérations arithmétiques).
Calcul du nombre d'opérations: On détermine la quantité d'opérations de base en fonction de $n$. Cela peut être une formule exacte ou une estimation.
Détermination de la classe asymptotique: On utilise les notations Big O ($O$), Omega ($\Omega$) et Theta ($\Theta$) pour décrire le comportement asymptotique supérieur, inférieur et précis, respectivement.
- $O(f(n))$: L'algorithme s'exécute en un temps qui ne dépasse pas une constante multipliée par $f(n)$ pour de grands $n$. Utilisé pour décrire le pire cas.
- $\Omega(f(n))$: L'algorithme s'exécute en un temps qui n'est pas inférieur à une constante multipliée par $f(n)$ pour de grands $n$. Utilisé pour décrire le meilleur cas.
- $\Theta(f(n))$: L'algorithme s'exécute en un temps proportionnel à $f(n)$ pour de grands $n$. Utilisé pour décrire le cas moyen ou lorsque le meilleur et le pire cas ont le même ordre asymptotique.

L'utilisation la plus courante est la Grande O ($O$) pour décrire la borne supérieure du temps d'exécution, ce qui est important pour comprendre la scalabilité de l'algorithme dans le pire scénario.

Omission des constantes et des termes de moindre ordre: Lors de la détermination de la notation asymptotique, on ignore les multiplicateurs constants et les termes de moindre ordre, car pour de grands $n$, la fonction avec le plus grand exposant domine. Par exemple, pour $3n^2 + 5n + 10$, la notation asymptotique sera $O(n^2)$.

Classes asymptotiques typiques (par ordre croissant de complexité):

$O(1)$: Complexité constante (le temps d'exécution ne dépend pas de $n$).
$O(\log n)$: Complexité logarithmique (le temps d'exécution croît très lentement avec $n$, caractéristique des algorithmes de recherche binaire).
$O(n)$: Complexité linéaire (le temps d'exécution est proportionnel à $n$, caractéristique de la recherche linéaire simple).
$O(n \log n)$: Complexité linéaire-logarithmique (typique pour des algorithmes de tri efficaces comme Quick Sort ou Merge Sort).
$O(n^2)$: Complexité quadratique (le temps d'exécution croît avec le carré de $n$, caractéristique des algorithmes de tri simples comme Bubble Sort).
$O(n^c)$ (pour $c > 1$): Complexité polynomiale.
$O(c^n)$ (pour $c > 1$): Complexité exponentielle (le temps d'exécution croît très rapidement avec $n$, typique pour la recherche exhaustive).
$O(n!)$: Complexité factorielle (la plus haute classe de complexité, croît extrêmement rapidement).

Pour déterminer la complexité asymptotique des structures cycliques:

Blocs de code séquentiels: La complexité des blocs s'additionne. $O(A+B) = O(\max(A, B))$.
Boucles imbriquées: Le nombre d'itérations se multiplie. Une boucle avec $n$ itérations à l'intérieur d'une autre avec $m$ itérations a une complexité $O(n \times m)$. Si $m=n$, alors $O(n^2)$.
Boucles avec réduction de la taille de l'entrée: Par exemple, diviser par 2 à chaque itération conduit à une complexité logarithmique ($O(\log n)$).

Exemple:

Parcours simple d'un tableau:

# Recompte des opérations de base (comparaisons, affectations)
# L'opération principale est la comparaison dans la boucle
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 affectation (hors boucle)
    for i in range(1, len(arr)): # La boucle s'exécute len(arr) - 1 fois
        # À l'intérieur de la boucle:
        # 1 comparaison (if arr[i] > max_val)
        # potentiellement 1 affectation (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

Si la taille du tableau est $n = \texttt{len(arr)}$, la boucle s'exécute $n-1$ fois. En chaque itération, un nombre constant d'opérations est effectué. Le nombre total d'opérations est proportionnel à $n$. Complexité asymptotique: $O(n)$.

Exemple: Tri par insertion (Insertion Sort)

# Recompte des opérations de base
# Opérations principales: comparaisons et affectations/déplacements d'éléments
def insertion_sort(arr):
    # La boucle externe s'exécute en $n-1$ fois
    for i in range(1, len(arr)):
        key = arr[i] # 1 affectation
        j = i - 1 # 1 affectation
        # La boucle interne s'exécute dans le pire cas $i$ fois
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 affectation (déplacement)
            j -= 1 # 1 soustraction et 1 affectation
        arr[j + 1] = key # 1 affectation

La boucle externe s'exécute $n-1$ fois. Dans le pire cas (le tableau est en ordre inverse), la boucle interne s'exécute en moyenne $i$ fois (ou jusqu'à $i$ fois). La somme des opérations sur toutes les itérations de la boucle externe est environ $1 + 2 + ... + (n-1) \approx n^2/2$. Complexité asymptotique: $O(n^2)$ dans le pire et le cas moyen, $O(n)$ dans le meilleur cas (tableau déjà trié). Lors de l'évaluation de la complexité, on considère généralement le pire cas (Grand $O$).

Comment évaluer la complexité d'un algorithme ou déterminer son asymptote?