Comprendre la notation Big O : guide du débutant sur la complexité temporelle et spatiale

Imaginez que nous ayons différentes manières d'écrire le même code. Comment déterminer lequel est le meilleur ? C'est là qu'intervient la notation Big O. Elle nous aide à mesurer le temps et l'espace dont le code aura besoin, ce qui facilitera sa comparaison.

Qu'est-ce que la notation Big-O ?

Big O, également connu sous le nom de « Ordre de », est un moyen de décrire le temps qu'un algorithme pourrait prendre pour s'exécuter dans le pire des cas. Cela nous donne une idée du temps maximum dont un algorithme aura besoin en fonction de la taille d'entrée. Nous l'écrivons sous la forme O(f(n)), où f(n) indique le nombre d'étapes nécessaires à l'algorithme pour résoudre un problème avec une taille d'entrée n.

Essayons de comprendre par un exemple "Écrivez une fonction qui accepte une entrée de chaîne et renvoie une copie inversée"

Très bien, je partage avec vous une solution Stack Overflow, ainsi que l'image ci-dessus, comme vous pouvez le voir. Il montre 10 façons différentes de résoudre le même problème, chacune avec une approche unique.

Maintenant, la question est : comment savoir lequel est le meilleur ?

Notre objectif est de comprendre la complexité du temps et de l'espace. Pour ce faire, explorons un exemple concret avec deux extraits de code différents, afin que nous puissions voir clairement l'importance de ces concepts.

Voici une fonction appelée addUpTo. Cette fonction utilise une boucle for qui s'exécute jusqu'à ce qu'elle atteigne la longueur de n et renvoie la somme totale.

Regardons maintenant un autre exemple qui réalise la même fonctionnalité :

Lequel est le meilleur ?

Maintenant, que signifie réellement « mieux » dans ce contexte ?

• Est-ce plus rapide ?

• Est-ce qu'il utilise moins de mémoire ?

• Est-ce plus lisible ?

En général, les gens se concentrent sur les deux premiers : la vitesse et l’utilisation de la mémoire – avant de considérer la lisibilité. Dans ce cas, nous nous concentrerons sur les deux premiers. Pour mesurer les performances des deux exemples de code, nous utiliserons les fonctions de synchronisation intégrées de JavaScript pour analyser et comparer leurs temps d'exécution.

Dans le code ci-dessus, j'ai ajouté t1 et t2, qui utilisent la fonction performance.now() intégrée à JavaScript. Cette fonction nous aide à mesurer le temps nécessaire à l'exécution du code, nous permettant de comparer avec précision les performances des deux approches.

Exactement, le temps d'exécution varie en fonction de différents facteurs, et vous pouvez également le constater sur mon ordinateur : les temps ne sont pas cohérents. La fonction performance.now() ne nous donne pas d'heure fixe, mais elle fournit une estimation utile à des fins de comparaison.

Maintenant, regardons le deuxième exemple :

Maintenant, observez la différence de temps d'exécution entre le premier et le deuxième exemple de code. Le second est sensiblement plus rapide que le premier.

Mais quel est le problème de se fier uniquement aux mesures du temps ?

• Différentes machines enregistrent des heures différentes.

• Même la même machine enregistrera des temps différents à chaque course.

• Pour les algorithmes très rapides, les mesures de vitesse peuvent ne pas être suffisamment précises pour donner une comparaison précise.

Ces facteurs rendent les évaluations de performances basées sur le temps peu fiables, en particulier pour les algorithmes rapides.

D'accord, si ce n'est pas l'heure, alors quoi ?

C’est là que Big O nous aidera à mesurer la complexité temporelle et spatiale à la fois. La notation Big O est donc un moyen de formaliser le comptage flou. Cela nous permet de parler formellement de la façon dont le temps d'exécution de l'algorithme augmente à mesure que l'entrée augmente.

Nous disons qu'un algorithme est O(f(n)) si le nombre d'opérations simples que l'ordinateur doit effectuer est finalement inférieur à une constante multipliée par f(n), à mesure que n augmente.

• f(n) pourrait être linéaire (f(n) = n)

• f(n) pourrait être quadratique (f(n) = n2)

• f(n) pourrait être constant (f(n) = 1)

• f(n) pourrait être quelque chose de complètement différent !

Voici un exemple :

Dans ce cas, nous n'avons que 3 opérations, et peu importe la taille de l'entrée, il restera toujours 3 opérations. C'est pourquoi on peut dire que la complexité temporelle de cette fonction est constante, ou O(1).

Voici maintenant le premier exemple :

Dans ce cas, à mesure que l'entrée n augmente, le nombre d'opérations augmente également proportionnellement. Par conséquent, la complexité temporelle dépend de la taille de l'entrée, ce qui en fait O(n).

Maintenant, regardons un autre exemple :

Dans cet exemple, nous avons deux boucles for imbriquées, toutes deux dépendantes de n : l'entrée. Cela signifie qu’à mesure que l’entrée n augmente, le nombre d’opérations augmente considérablement. En conséquence, la complexité temporelle de ce code est O(n²), également connue sous le nom de complexité temporelle quadratique.

Maintenant, simplifions la Big O Notation. Lors de la détermination de la complexité temporelle d’un algorithme, il convient de garder à l’esprit quelques règles empiriques utiles. Ces lignes directrices découlent de la définition formelle de la notation Big O et facilitent l'analyse des algorithmes.

Les constantes n'ont pas d'importance

• O(2n) = O(n)

• O(500) = O(1)

• O(13n²) = O(n²)

• O(n 10) = O(n)

• O(1000n 500) = O(n)

• O(n² 5n 8) = O(n²)

Big O sténographies

1. Les opérations arithmétiques sont constantes

2. L'affectation des variables est constante

3. L'accès aux éléments d'un tableau (par index) ou d'un objet (par clé) est constant

4. Dans une boucle, la complexité est la longueur de la boucle multipliée par la complexité de tout ce qui se passe à l'intérieur de la boucle

Voici le Big O Chart :

Jusqu'à présent, à partir des exemples, nous avons appris O(n) (complexité temporelle linéaire), O(1) (complexité temporelle constante) et O(n²) (complexité temporelle quadratique). Ceux-ci couvrent les modèles de base dans lesquels les opérations augmentent avec la taille des entrées.

Nous discuterons de O(log n) et O(n log n)—les complexités temporelles logarithmiques et linéaires—un peu plus tard.

Complexité spatiale

Jusqu'à présent, nous nous sommes concentrés sur la complexité temporelle : comment analyser le temps d'exécution d'un algorithme à mesure que la taille des entrées augmente ?

Nous pouvons également utiliser la notation grand O pour analyser la complexité de l'espace : quelle quantité de mémoire supplémentaire devons-nous allouer pour exécuter le code dans notre algorithme ?

Et les entrées ?

Parfois, vous entendrez le terme complexité de l'espace auxiliaire pour désigner l'espace requis par l'algorithme, sans compter l'espace occupé par les entrées. Sauf indication contraire, lorsque nous parlons de complexité spatiale, techniquement, nous parlerons de complexité spatiale auxiliaire.

Complexité spatiale en JS

• La plupart des primitives (booléens, nombres, indéfinis, nuls) 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 sont généralement O(n), où n est la longueur (pour les tableaux) ou le nombre de clés (pour les objets)

N'oubliez pas que nous parlons de complexité spatiale, pas de complexité temporelle. Dans ce code, nous pouvons voir que nous n’avons que deux variables. Quelle que soit la taille de l'entrée, ces deux variables existeront toujours dans le code. Puisque nous n'ajoutons aucune nouvelle variable à mesure que l'entrée augmente, nous pouvons dire que la complexité spatiale est O(1), ce qui signifie que c'est une complexité spatiale constante.

Comprenons avec un autre exemple :

Dans ce code, la fonction renvoie newArr après avoir doublé chaque élément du tableau d'entrée. Étant donné que la taille de newArr est directement proportionnelle à la taille de l'arr d'entrée, l'espace utilisé par newArr augmente avec la taille d'entrée. Contrairement à l'exemple précédent, où l'espace était constant, ici la complexité de l'espace dépend de la taille du tableau d'entrée. Par conséquent, la complexité spatiale est O(n), ce qui signifie qu'elle est linéaire.

J'espère que cela rend la complexité spatiale plus claire : tout comme la complexité temporelle, nous la mesurons en utilisant la notation Big O. Jusqu'à présent, vous avez découvert différentes complexités temporelles, par ordre croissant de complexité : O(1), O(log n), O(n), O(n log n), O(n²), O(n³), et ainsi de suite. Cependant, nous n'avons pas encore exploré la complexité temporelle logarithmique.

Ensuite, nous plongerons dans la complexité temporelle logarithmique et verrons comment cela fonctionne.

Logarithmes

Nous avons rencontré certaines des complexités les plus courantes : O(1), O(n), O(n2). Parfois, les expressions en grand O impliquent des expressions mathématiques plus complexes. Celui qui apparaît plus souvent que vous ne le souhaiteriez est le logarithme !

Qu'est-ce qu'un journal déjà ?

log2 (8) = 3 → 2³ = 8

log2 (valeur) = exposant → 2^exposant = valeur

On omettra le 2, ce qui veut dire :

log === log2

Le logarithme d'un nombre mesure approximativement combien de fois vous pouvez diviser ce nombre par 2 avant qu'il ne devienne inférieur ou égal à 1. Cela rend la complexité temporelle logarithmique très efficace. Comme vous l'avez vu dans le graphique, O(1) (temps constant) est très proche de O(log n), ce qui est fantastique ! Il convient également de noter que O(n log n) est bien meilleur que O(n²) en termes d'efficacité, ce qui en fait une complexité privilégiée pour de nombreux algorithmes.

• Certains algorithmes de recherche ont une complexité temporelle logarithmique.

• Les algorithmes de tri efficaces impliquent des logarithmes.

• La récursivité implique parfois une complexité spatiale logarithmique.

Super ! Nous avons couvert la plupart des points clés sur la complexité spatiale et temporelle. Gardez à l’esprit que la maîtrise de ces concepts demande de la pratique, alors ne vous sentez pas dépassé si ce n’est pas tout de suite clair. Prenez votre temps, relisez le matériel plusieurs fois et revisitez les exemples si nécessaire. Il faut souvent quelques répétitions pour que ces idées soient vraiment intégrées, alors soyez patient avec vous-même !

Enfin, faisons un dernier récapitulatif :

• Pour analyser les performances d'un algorithme, nous utilisons Big O Notation

• Big O Notation peut nous donner une compréhension de haut niveau de la complexité temporelle ou spatiale d'un algorithme

• Big O Notation ne se soucie pas de la précision, seulement des tendances générales (linéaire ? quadratique ? constante ?)

Encore une fois, la notation Big O est partout, alors entraînez-vous beaucoup !

---

Chez CreoWis, nous croyons au partage public des connaissances pour aider la communauté des développeurs à se développer. Collaborons, créons des idées et créons notre passion pour offrir au monde des expériences produits impressionnantes.

Connectons-nous :

• X/Twitter

• LinkedIn

• Site Internet

Cet article est rédigé par Syket Bhattachergee, un développeur passionné chez CreoWis. Vous pouvez le contacter sur X/Twitter, LinkedIn, et suivre son travail sur le GitHub.

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!