Maison > Article > interface Web > 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.
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é.
Explorons deux façons de calculer la somme de tous les nombres de 1 à n :
function addUpTo(n) { let total = 0; for (let i = 1; i <= n; i++) { total += i; } return total; }
function addUpTo(n) { return n * (n + 1) / 2; }
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 :
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).
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 :
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).
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).
Analyser tous les aspects de la complexité du code peut être complexe, mais certaines règles générales peuvent simplifier les choses :
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.
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.
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!