Notation Big O

En savoir plus sur Big O Notation, un processus mathématique que nous pouvons utiliser pour mesurer les performances et la complexité d'un algorithme.

Lorsque nous commençons à apprendre la programmation, en commençant à écrire nos premiers algorithmes, il est courant d'écrire code qui n'est ni performatif ni lisible. Le fait de vous souvenir de vos premières lignes de code dans votre langage de programmation préféré peut vous causer des cauchemars sur la façon dont vous faisiez certaines choses à l'époque et comment vous faites ces mêmes choses aujourd'hui.

Au fur et à mesure que nous en apprenons davantage sur la programmation, notre expérience augmente constamment notre façon de résoudre les problèmes s'améliore constamment, au fur et à mesure que nous progressons, nous apprenons quelque chose de nouveau chaque jour. Programmer ne signifie pas taper quelques mots dans un éditeur et cela se transformera par magie en programme. Il y a beaucoup de travail derrière cela, beaucoup d'outils et de concepts que les développeurs doivent apprendre, afin d'écrire le meilleur code, le plus performant, le plus lisible et le plus gérable.

Big O Notation peut nous faire gagner un temps précieux en nous aider à écrire un meilleur code. Nous utilisons ce processus mathématique depuis longtemps. Même si vous ne savez pas grand-chose sur ce processus, vous en avez peut-être déjà entendu parler.

Je vais vous montrer comment vous pouvez, même si vous n'êtes pas un expert en mathématiques, mesurer les performances et la complexité de votre algorithme , et améliorez-le facilement en suivant quelques étapes.

Qu'est-ce que Big O Notation?

Parfois, les développeurs peuvent entendre le terme «Big O Notation» et avoir peur, car ils pensent que ce concept est peut-être trop complexe. Bien que la définition Wikipedia de la notation Big O puisse être un peu complexe pour les débutants, le processus mathématique lui-même n'est pas si complexe.

Il existe de nombreuses façons différentes d'expliquer ce qu'est la Big O Notation et pourquoi elle existe. Voici comment définir la notation Big O en une phrase simple:

Big O Notation est une représentation de la complexité d'un algorithme.

C'est un processus mathématique qui nous permet de mesurer la performance et la complexité de notre algorithme.

Habituellement, Big O Notation utilise deux facteurs pour analyser un algorithme:

● Time Complexity —Combien de temps faut-il à un algorithme pour s'exécuter
● Complexité spatiale – La mémoire requise par l'algorithme

À mesure que nos entrées augmentent, le temps d'exécution de cet algorithme reste-t-il le même? Ce code sera-t-il évolutif, ce qui signifie que nous devrons nous soucier des performances de ce code à l'avenir?

Habituellement, les gens aiment mesurer la qualité d'un code par sa lisibilité. Bien que toujours un paramètre valide, la lisibilité à elle seule ne garantit pas que ce que vous avez écrit peut être considéré comme du bon code.

En général, lorsque vous travaillez dans un projet, vous aurez beaucoup de fonctions différentes, et différentes fonctions ont des complexités Big O différentes. Nous pouvons facilement comparer deux algorithmes différents en utilisant la notation Big O et dire lequel est le meilleur.

Une bonne chose à savoir est que Big O Notation ne mesure pas les choses en quelques secondes. Au lieu de cela, il considère toujours le pire des cas, c'est-à-dire la vitesse à laquelle notre runtime croît.

Découvrons maintenant les différents types de complexité temporelle dans Big O Notation et voyons les différences entre eux.

O (1)

Un algorithme aura une complexité de temps constant lorsqu'il s'exécute dans le même laps de temps, quelle que soit la taille d'entrée.

Imaginons que nous ayons une fonction qui prend un tableau d'entrée de trois items, et nous voulons retourner le premier élément de ce tableau chaque fois que nous appelons la fonction.

 const  arr  =   [ 1   2  ]  3 ] ; 
 function   logTwoFirstItems  ( items )   {
 console .  log  ( items  [ 0 ] ) ; 
} ; 
 logTwoFirstItems [19659024] ( arr ) ; 

Quelle que soit la taille du tableau, notre fonction s'exécutera toujours dans le même laps de temps. Le temps constant est considéré comme le meilleur scénario pour un algorithme.

Dans Big O Notation, O représente l'ordre de grandeur, et ce qui est entre parenthèses représente la complexité d'une tâche. C'est pourquoi nous avons utilisé O (1) pour montrer que ce code a une complexité temps constant .

O (log n)

Un logarithme est une opération mathématique qui détermine combien de fois un certain nombre, appelé la base, est multiplié par lui-même pour atteindre un autre nombre. Une fonction logarithmique est l'opposé d'une fonction exponentielle.

Un algorithme aura une complexité temps logarithmique lorsque le temps d'exécution croît linéairement tandis que la taille d'entrée croît exponentiellement.

Imaginez que nous prenions une seconde pour calculer un tableau d'entrée de 10 éléments. Comme la complexité temporelle croîtrait linéairement, nous prendrions deux secondes pour calculer un tableau d'entrée de 20 éléments, trois secondes pour un tableau d'entrée de 30 éléments, etc.

Un algorithme qui a une complexité temporelle logarithmique est le binaire algorithme de recherche .

L'algorithme de recherche binaire est un algorithme très efficace pour trouver un élément dans une liste triée d'éléments.

Imaginez que vous vouliez rechercher un élément spécifique dans une énorme liste de 10 000 éléments. Si nous parcourons cette liste et comparons chaque élément avec l'élément spécifique que nous voulions renvoyer, cet algorithme aurait une complexité de temps linéaire (que nous en apprendrons plus dans la section suivante). [19659003] L'algorithme de recherche binaire fonctionne différemment. Au lieu de parcourir la liste et de comparer chaque élément, il divise la liste par deux plages de même taille.

À chaque étape, l'algorithme choisira l'élément central du tableau et le comparera à l'élément. Si les éléments correspondent, l'élément est renvoyé. Il divisera à plusieurs reprises la plage en deux et recherchera l'élément souhaité jusqu'à ce qu'il trouve l'élément.

O (n)

Un algorithme aura une complexité temps linéaire lorsque l'exécution de l'algorithme change linéairement avec la taille d'entrée.

Prenons comme exemple une fonction qui reçoit un tableau d'entrée avec quatre éléments seulement, et nous voulons mapper ce tableau d'entrée et vérifier un élément spécifique. ] arr = nouveau Array ( 4 ) . fill ( "bonjour" ) [19659024];
function findHello ( arr ) {
for ( let i = 0 ; i < arr . length ; i ++ ) {
if [19659022] ( arr [ i ] === «bonjour» [19659024]) {
console . log ( 'hello!' ) ;
}
}
}
findHello ( large ) ;

Au fur et à mesure que la taille d'entrée change, le nombre d'opérations change également – c'est ce qu'on appelle la complexité temps linéaire .

Si nous avions un tableau d'entrée de 10 000

Chaque fois que nous voyons une boucle, nous pouvons considérer cet algorithme comme une complexité temporelle linéaire.

O (n ^ 2)

Un algorithme a un ] temps quadratique complexité lorsque le temps d'exécution est proportionnel au carré de la taille de l'entrée.

Imaginons que nous ayons un tableau d'entrée, et pour chaque élément de ce tableau, nous bouclerons à nouveau pour comparer le courant élément avec les autres éléments du tableau.

 const  arr  =   new   Array  ( 4 ) .  fill [19659024] ([19659068] 'hello' ) ; 
 const  newArr  =   new   Array  ( 4 ) . [19659034] fill  ( 'hello' ) ; 
 function   findHello  ( arr )   {
  for [19659022] ( let  i  =   0 ;  i  < arr .  length ;  i  ++ )   {
    for   ( let  j  =   0 ;  j  <  newArr .  length ;  j  ++ )   {
      if   ( arr  [ i ]   ===  newArr  [ j ] )   {
       console .  log  ( 'hello!' ) ; 
     } 
   } 
 } 
} 
 findHello [19659024] ( large ) ; 

Chaque fois que nous voyons des boucles imbriquées, nous utilisons la multiplication. Chaque fois que le nombre d'éléments augmente, la complexité augmente de façon quadratique.

C'est vraiment quelque chose auquel vous devriez faire attention si vous avez plus de deux boucles imbriquées – c'est vraiment un mauvais code et vous faites probablement quelque chose de mal.

O (n!)

Un algorithme de complexité temps factoriel trouve toutes les permutations d'un ensemble / chaîne donné. Il atteint l'infini beaucoup plus rapidement que les autres types de complexités, et rappelez-vous que l'infini est l'ennemi de la performance.

Factorial, "oh non!" Cela signifie que nous ajoutons une boucle imbriquée pour chaque entrée que nous avons – un grand non-non.

Vous ne la verrez probablement jamais, mais il est bon de savoir qu'elle existe.

Wrapping Up

L'optimisation prématurée peut être à l'origine de tous les maux. Parfois, l'optimisation pour le temps ou l'espace peut avoir un impact négatif sur la lisibilité de votre code, surtout si vous ne savez pas exactement ce que vous faites.

Lorsque nous écrivons du code, nous voulons écrire du code qui évolue, de sorte que nous ne le faisons pas. doivent constamment revenir en arrière et corriger les choses au fur et à mesure que nos applications grandissent. Big O est un processus mathématique important qui peut nous aider à écrire du code évolutif, à penser à long terme et à nous éviter d'éventuels problèmes à l'avenir.

Essayez de comprendre le code sur lequel vous travaillez, comment les choses sont en cours, comment vous pouvez améliorer de telles choses, et cela produira un meilleur résultat à l'avenir, vous aidant à économiser de l'argent et du temps.

Conclusion

La ​​complexité de l'espace et du temps sont des choses importantes auxquelles nous devons prêter attention sur un base quotidienne. La façon dont nous écrivons notre code peut influencer les performances et le succès de nos applications. Ecrire du code capable de fonctionner à l'échelle de plusieurs millions n'est pas une tâche facile, mais c'est certainement quelque chose qui devrait être encouragé par les développeurs.