Guide du débutant pour la notation Big O

Big O Notation est un moyen de représenter la durée d'exécution d'un algorithme. Il permet à un ingénieur logiciel de déterminer l'efficacité des différentes approches pour résoudre un problème.

Voici quelques types courants de complexités temporelles dans Big O Notation.

  • O (1) - Complexité en temps constant
  • O (n) - Complexité temporelle linéaire
  • O (log n) - Complexité temporelle logarithmique
  • O (n ^ 2) - Complexité temporelle quadratique

J'espère qu'à la fin de cet article, vous serez en mesure de comprendre les bases de Big O Notation.

O (1) - Temps constant

Les algorithmes à temps constant prendront toujours le même temps pour être exécutés. Le temps d'exécution de ces algorithmes est indépendant de la taille de l'entrée. Un bon exemple de temps O (1) est l'accès à une valeur avec un index de tableau.

var arr = [ 1,2,3,4,5];
arr[2]; // => 3

D'autres exemples incluent: les opérations push () et pop () sur un tableau.

O (n) - Complexité temporelle linéaire

Un algorithme a une complexité temporelle linéaire si le temps d'exécution de l'algorithme est directement proportionnel à la taille d'entrée n . Par conséquent, le temps qu'il faudra pour exécuter l'algorithme augmentera proportionnellement à mesure que la taille de l'entrée n augmente.

Un bon exemple est de trouver un CD dans une pile de CD ou de lire un livre, où n est le nombre de pages.

Des exemples de O (n) utilisent la recherche linéaire:

//if we used for loop to print out the values of the arrays
for (var i = 0; i < array.length; i++) { console.log(array[i]);}
var arr1 = [orange, apple, banana, lemon]; //=> 4 steps
var arr2 = [apple, htc,samsung, sony, motorola]; //=> 5 steps

O (log n) - Complexité temporelle logarithmique

Un algorithme a une complexité temporelle logarithmique si le temps nécessaire pour exécuter l'algorithme est proportionnel au logarithme de la taille d'entrée n . Un exemple est la recherche binaire, qui est souvent utilisée pour rechercher des ensembles de données:

//Binary search implementationvar doSearch = function(array, targetValue) { var minIndex = 0; var maxIndex = array.length - 1; var currentIndex; var currentElement; while (minIndex <= maxIndex) { currentIndex = (minIndex + maxIndex) / 2 | 0; currentElement = array[currentIndex]; if (currentElement  targetValue) { maxIndex = currentIndex - 1; } else { return currentIndex; } } return -1; //If the index of the element is not found.};
var numbers = [11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33];
doSearch(numbers, 23) //=>; 6

D'autres exemples de complexité temporelle logarithmique comprennent:

Example 1;
for (var i = 1; i < n; i = i * 2) console.log(i);}
Example 2;
for (i = n; i >= 1; i = i/2) console.log(i);}

O (n ^ 2) - Complexité temporelle quadratique

Un algorithme a une complexité temporelle quadratique si le temps d'exécution est proportionnel au carré de la taille d'entrée. Un bon exemple de ceci est de vérifier s'il y a des doublons dans un jeu de cartes.

Vous rencontrerez une complexité temporelle quadratique dans les algorithmes impliquant des itérations imbriquées, telles que les boucles for imbriquées . En fait, les boucles imbriquées plus profondes donneront O (n ^ 3), O (n ^ 4), etc.

for(var i = 0; i < length; i++) { //has O(n) time complexity for(var j = 0; j < length; j++) { //has O(n^2) time complexity // More loops? }}

D'autres exemples de complexité temporelle quadratique incluent le tri par bulles, le tri par sélection et le tri par insertion.

Cet article ne fait qu'effleurer la surface de Big O Notation. Si vous souhaitez en savoir plus sur Big O Notation, je vous recommande de consulter le Big-O Cheat Sheet.