Notation Big O : un guide simple

Big O Notation est un concept mathématique utilisé pour décrire les performances ou la complexité d'un algorithme en termes de temps et d'espace à mesure que la taille d'entrée augmente. Cela nous aide à comprendre comment le temps d'exécution d'un algorithme augmente avec des entrées plus importantes, permettant une comparaison plus standardisée de différents algorithmes.

Pourquoi utiliser la notation Big O ?

Lors de la comparaison d'algorithmes, se fier uniquement au temps d'exécution peut être trompeur. Par exemple, un algorithme peut traiter un ensemble de données volumineux en une heure, tandis qu’un autre prend quatre heures. Cependant, le temps d'exécution peut varier en fonction de la machine et des autres processus en cours d'exécution. Au lieu de cela, nous utilisons Big O Notation pour nous concentrer sur le nombre d'opérations effectuées, ce qui fournit une mesure plus cohérente de l'efficacité.

Exemple : additionner des nombres

Explorons deux façons de calculer la somme de tous les nombres de 1 à n :

Option 1 : Utiliser une boucle

function addUpTo(n) {
    let total = 0;
    for (let i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

Option 2 : Utiliser une formule

function addUpTo(n) {
    return n * (n + 1) / 2;
}

Analyser la complexité

Dans l'option 1, si n vaut 100, la boucle s'exécute 100 fois. En revanche, l'option 2 exécute toujours un nombre fixe d'opérations (multiplication, addition et division). Ainsi :

• L'option 1 est O(n) : la complexité temporelle croît linéairement avec n.
• L'option 2 est O(1) : la complexité temporelle reste constante, quelle que soit la taille d'entrée.

Avis de non-responsabilité

Alors que l'option 2 implique trois opérations (multiplication, addition, division), nous nous concentrons sur la tendance générale de l'analyse Big O. Ainsi, au lieu de l’exprimer sous la forme O(3n), nous le simplifions en O(n). De même, O(n 10) se simplifie en O(n) et O(n^2 5n 8) se simplifie en O(n^2). Dans Big O Notation, nous considérons le pire des cas, où le terme d'ordre le plus élevé a le plus grand impact sur les performances.

Il existe d'autres formes de notation au-delà des complexités courantes énumérées ci-dessus, telles que la complexité temporelle logarithmique exprimée sous la forme O(log n).

Qu’est-ce que la notation Big O ?

Big O Notation nous permet de formaliser la croissance du temps d'exécution d'un algorithme en fonction de la taille des entrées. Plutôt que de nous concentrer sur des nombres d'opérations spécifiques, nous catégorisons les algorithmes en classes plus larges, notamment :

• Temps constant : O(1) - Les performances de l'algorithme ne changent pas avec la taille d'entrée.
• Temps linéaire : O(n) - Les performances augmentent linéairement avec la taille d'entrée.
• Temps quadratique : O(n^2) - Les performances augmentent de manière quadratique à mesure que la taille d'entrée augmente.

Exemple de O(n^2)

Considérons la fonction suivante, qui imprime toutes les paires de nombres de 0 à n :

function addUpTo(n) {
    let total = 0;
    for (let i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

Dans ce cas, la fonction a deux boucles imbriquées, donc lorsque nnn augmente, le nombre d'opérations augmente quadratiquement. Pour n= 2, il y a 4 opérations, et pour n=3, il y a 9 opérations, menant à O(n^2).

Un autre exemple : comptez de haut en bas

function addUpTo(n) {
    return n * (n + 1) / 2;
}

À première vue, on pourrait penser qu'il s'agit de O(n^2) car il contient deux boucles. Cependant, les deux boucles s'exécutent indépendamment et évoluent linéairement avec n. Ainsi, la complexité temporelle globale est O(n).

Simplifier l'analyse

Analyser tous les aspects de la complexité du code peut être complexe, mais certaines règles générales peuvent simplifier les choses :

• Les opérations arithmétiques sont considérées comme un temps constant.
• Les affectations variables sont à temps constant.
• L'accès aux éléments d'un tableau (par index) ou d'un objet (par clé) est en temps constant.
• Pour une boucle, la complexité est la longueur de la boucle multipliée par la complexité de ce qui se passe à l'intérieur de la boucle.

Complexité spatiale

Bien que nous nous soyons concentrés sur la complexité temporelle, il est également possible de calculer la complexité spatiale (mémoire) à l'aide de Big O. Certaines personnes incluent la taille d'entrée dans leurs calculs, mais il est souvent plus utile de se concentrer uniquement sur l'espace requis par l'algorithme. lui-même.

Règles pour la complexité spatiale (basées sur JavaScript) :

• La plupart des valeurs primitives (booléennes, nombres, etc.) sont des espaces constants.
• Les chaînes nécessitent un espace O(n) (où n est la longueur de la chaîne).
• Les types de référence (tableaux, objets) sont généralement O(n), où n est la longueur du tableau ou le nombre de clés dans l'objet.

Un exemple

function printAllPairs(n) {
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
            console.log(i, j);
        }
    }
}

Dans cette fonction, la complexité spatiale est O(1) car nous utilisons une quantité constante d'espace (deux variables) quelle que soit la taille d'entrée.

Pour une fonction qui crée un nouveau tableau :

function countUpAndDown(n) {
    console.log("Going up!");
    for (var i = 0; i < n; i++) {
        console.log(i);
    }
    console.log("At the top!\nGoing down...");
    for (var j = n - 1; j >= 0; j--) {
        console.log(j);
    }
    console.log("Back down. Bye!");
}

Ici, la complexité spatiale est O(n) car nous allouons de l'espace pour un nouveau tableau qui grandit avec la taille du tableau d'entrée.

Conclusion

Big O Notation fournit un cadre pour analyser l'efficacité des algorithmes d'une manière indépendante du matériel et des détails spécifiques de mise en œuvre. Comprendre ces concepts est crucial pour développer un code efficace, en particulier à mesure que la taille des données augmente. En se concentrant sur l'évolution des performances, les développeurs peuvent faire des choix éclairés sur les algorithmes à utiliser dans leurs applications.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!