date: 2023-10-16
Type: Cours
Projet: Blindcode
Cours: Algorithmie

La Notation Big O

Header :

La notation Big O est un outil essentiel dans l'analyse de la complexité des algorithmes. Elle permet de décrire de manière formelle la façon dont le temps d'exécution (complexité temporelle) ou l'utilisation de la mémoire (complexité spatiale) d'un algorithme augmente en fonction de la taille de l'entrée. Voici comment fonctionne la notation Big O :

Body

1. Notation O(f(n))

La notation Big O, souvent représentée comme O(f(n)), est utilisée pour exprimer la complexité d'un algorithme en fonction de la taille de l'entrée (n). La fonction f(n) représente la croissance de l'algorithme, indiquant comment le temps d'exécution ou l'utilisation de la mémoire augmente lorsque la taille de l'entrée augmente.

2. Exemples Courants

Voici quelques exemples courants de notations Big O :

O(1) : Complexité constante. Le temps d'exécution est indépendant de la taille de l'entrée. Par exemple, l'accès à un élément dans un tableau.
O(log n) : Complexité logarithmique. Le temps d'exécution augmente de manière logarithmique avec la taille de l'entrée. Par exemple, la recherche binaire.
O(n) : Complexité linéaire. Le temps d'exécution est proportionnel à la taille de l'entrée. Par exemple, la recherche séquentielle.
O(n log n) : Complexité linéarithmique. Courante dans de nombreux algorithmes de tri.
O(n^2) : Complexité quadratique. Le temps d'exécution est le carré de la taille de l'entrée. Par exemple, le tri par insertion.
O(2^n) : Complexité exponentielle. Le temps d'exécution augmente de manière exponentielle avec la taille de l'entrée.

3. Notation du Pire des Cas

La notation Big O est souvent utilisée pour exprimer la complexité du pire des cas (worst-case scenario) d'un algorithme. Cela garantit que l'algorithme fonctionnera efficacement dans toutes les situations, même dans les scénarios les plus défavorables.

4. Comparaison et Sélection d'Algorithmes

La notation Big O est précieuse pour comparer et sélectionner des algorithmes en fonction de leurs performances. Lorsqu'on doit choisir entre plusieurs solutions pour un problème donné, il est judicieux de choisir l'algorithme avec la complexité temporelle la plus faible pour garantir des performances optimales.

5. Exemples et Calculs de la Notation Big O

Voyons quelques exemples concrets d'algorithmes et de leurs notations Big O correspondantes :

a. Complexité O(1) (Constante)

Exemple : Accéder à un élément dans un tableau.

FONCTION accesTableau(tableau : TABLEAU, index : ENTIER) : ELEMENT
    RETOURNER tableau[index]
FIN FONCTION

La complexité est constante (O(1)) car le temps d'accès ne dépend pas de la taille du tableau. (Dans un cas réel il faudrait traiter le out of index, mais c'est un détail et ça marche quand même de la même façon).

b. Complexité O(n) (Linéaire)

Exemple : Recherche séquentielle dans un tableau non trié.

FONCTION rechercheSequentielle(tableau : TABLEAU, element : ELEMENT) : ENTIER
    POUR index DE 0 À LONGUEUR(tableau) - 1 FAIRE
        SI tableau[index] = element ALORS
            RETOURNER index
        FIN SI
    FIN POUR
    RETOURNER -1
FIN FONCTION

La complexité est linéaire (O(n)) car, dans le pire des cas, il faut parcourir tout le tableau pour trouver l'élément recherché.

c. Complexité O(log n) (Logarithmique)

Exemple : Recherche binaire dans un tableau trié.

FONCTION rechercheBinaire(tableau : TABLEAU_TRIE, element : ELEMENT) : ENTIER
    DEBUT <- 0
    FIN <- LONGUEUR(tableau) - 1
    TANT QUE DEBUT <= FIN FAIRE
        milieu <- (DEBUT + FIN) / 2
        SI tableau[milieu] = element ALORS
            RETOURNER milieu
        SINON SI tableau[milieu] < element ALORS
            DEBUT <- milieu + 1
        SINON
            FIN <- milieu - 1
        FIN SI
    FIN TANT QUE
    RETOURNER -1
FIN FONCTION

La complexité est logarithmique (O(log n)) car, à chaque étape, la recherche divise la plage de recherche par deux.

d. Complexité O(n^2) (Quadratique)

Exemple : Tri par insertion.

FONCTION triInsertion(tableau : TABLEAU) : TABLEAU
    POUR i DE 1 À LONGUEUR(tableau) - 1 FAIRE
        valeur <- tableau[i]
        j <- i
        TANT QUE j > 0 ET tableau[j - 1] > valeur FAIRE
            tableau[j] <- tableau[j - 1]
            j <- j - 1
        FIN TANT QUE
        tableau[j] <- valeur
    FIN POUR
    RETOURNER tableau
FIN FONCTION

La complexité est quadratique (O(n^2)) car, dans le pire des cas, chaque élément doit être comparé avec tous les éléments précédents et déplacé à sa position correcte.

e. Complexité O(2^n) (Exponentielle)

Exemple : Génération de toutes les sous-séquences d'une séquence.

FONCTION sousSequences(sequence : TABLEAU) : TABLEAU_DE_TABLEAUX
    SI LONGUEUR(sequence) = 0 ALORS
        RETOURNER [ [] ]  // Cas de base
    SINON
        sousSeqSansPremier <- sousSequences(SUPPRIMER_PREMIER_ELEMENT(sequence))
        premiereValeur <- PREMIER_ELEMENT(sequence)
        nouvellesSousSeq <- CLONER(sousSeqSansPremier)
        POUR chaque sousSeq DANS sousSeqSansPremier FAIRE
            AJOUTER premiereValeur AU DEBUT DE sousSeq
            AJOUTER sousSeq À nouvellesSousSeq
        FIN POUR
        RETOURNER CONCATENER(nouvellesSousSeq, sousSeqSansPremier)
    FIN SI
FIN FONCTION

La complexité est exponentielle (O(2^n)) car le nombre de sous-séquences possibles double à chaque ajout d'élément à la séquence. Prenez un peut le comprendre tous ces exemples, il est normal de ne pas tous les saisir à la première lecture !

Ces exemples illustrent diverses notations Big O en fonction de la croissance du temps d'exécution par rapport à la taille de l'entrée. La compréhension de ces notations est essentielle pour évaluer et comparer les performances des algorithmes.

La notation Big O est un outil puissant pour analyser la complexité des algorithmes, ce qui permet de concevoir des solutions efficaces pour des problèmes de toutes tailles. Elle est couramment utilisée par les informaticiens et les développeurs pour évaluer les performances et l'efficacité des algorithmes dans une variété de domaines, de la conception de logiciels à l'optimisation des bases de données.