La complexité des algorithmes simples et des structures de données dans JS

Dans l'article précédent «Un pas vers l'informatique en tant que science: algorithmes simples et structures de données dans JS», nous avons discuté des algorithmes simples (recherches linéaires et binaires; bulles, tri de sélection et d'insertion) et des structures de données (tableaux et objets appariés clé-valeur ). Ici, je continue avec le concept de complexité et son application à ces algorithmes et structures de données.

Complexité

La complexité est un facteur impliqué dans un processus complexe. En ce qui concerne les algorithmes et les structures de données, cela peut être le temps ou l' espace (c'est-à-dire la mémoire de calcul) nécessaire pour effectuer une tâche spécifique (rechercher, trier ou accéder aux données) sur une structure de données donnée. L'efficacité de l'exécution d'une tâche dépend du nombre d'opérations requises pour terminer une tâche.

Sortir la poubelle peut nécessiter 3 étapes (attacher un sac à ordures, le sortir et le déposer dans une poubelle). Sortir la poubelle peut être simple, mais si vous sortez la poubelle après une longue semaine de rénovation, vous risquez de ne pas pouvoir terminer la tâche en raison d'un manque d'espace dans la benne à ordures.

Passer l'aspirateur dans une pièce peut nécessiter de nombreuses étapes répétitives (l'allumer, balayer à plusieurs reprises la tête d'aspiration sur un sol et l'éteindre). Plus une pièce est grande, plus vous devrez balayer une tête d'aspirateur sur son sol. Ainsi, plus le temps qu'il faudra pour passer l'aspirateur dans la pièce est long .

Il existe donc une relation causale directe entre le nombre d'opérations effectuées et le nombre d'éléments sur lesquels sont exécutées. Avoir beaucoup de déchets (éléments) nécessite de les retirer plusieurs fois. Cela peut conduire à un problème de complexité spatiale . Avoir beaucoup de pieds carrés (éléments) nécessite de balayer plusieurs fois une tête d'aspiration sur un sol. Cela peut conduire à un problème de complexité temporelle .

Que vous sortiez les poubelles ou que vous passiez l'aspirateur dans une pièce , vous pourriez dire que le nombre d'opérations ( O ) augmente exactement avec le nombre d'éléments ( n ) . Si j'ai 1 sac poubelle, je dois sortir la poubelle une fois. Si j'avais 2 sacs poubelle, je dois effectuer la même tâche deux fois, en supposant que vous ne puissiez pas soulever physiquement plus d'un sac à la fois. Ainsi, le Big-O de ces tâches est O = n ou O = fonction (n) ou O (n) . Il s'agit d'une complexité linéaire (une ligne droite avec une correspondance 1 opération: 1 élément). Ainsi, 30 opérations sont effectuées sur 30 éléments (ligne jaune sur le graphique).

Ceci est similaire à ce qui se passe lors de l'examen des algorithmes et des structures de données.

Recherches

Recherche linéaire

Le meilleur cas pour rechercher un élément dans une liste ordonnée, l'un après l'autre, est une constante O (1) , en supposant qu'il s'agit du 1er élément de votre liste. Ainsi, si l'article que vous recherchez est toujours répertorié en premier, quelle que soit la taille de votre liste, vous trouverez votre article en un instant. La complexité de votre recherche est constante avec la taille de la liste. La moyenne au pire des cas de ce type de recherche est une complexité linéaire ou O (n). En d'autres termes,pour n articles, je dois chercher n fois avant de trouver mon article, d'où une recherche linéaire.

Recherche binaire

Pour une recherche binaire, le meilleur des cas est O (1), ce qui signifie que l'élément de votre recherche est situé au milieu. Le pire et moyen cas est le log base 2 de n ou:

Le logarithme ou log est une manière d'exprimer un exposant pour une base donnée. Donc, s'il y avait 16 éléments (n = 16), alors il faudrait, dans le pire des cas, 4 étapes pour trouver le nombre 15 (exposant = 4).

Ou simplement: O (log n)

Trie

Bulle

Dans le tri à bulles, chaque élément est comparé au reste de la collection pour déterminer la valeur la plus élevée à gonfler. Pour cette raison, en moyenne au pire des cas , sa complexité est O (n²) . Pensez à une boucle imbriquée dans une autre boucle.

Donc, pour chaque article, vous le comparez au reste de votre collection. Cela équivaut à 16 comparaisons (ou opérations) pour 4 éléments (4² = 16). Le meilleur des cas est si votre collection est presque triée, sauf pour un seul élément. Cela équivaudrait à une seule série de comparaisons. Autrement dit, quatre comparaisons sont nécessaires pour faire remonter un membre d'une collection de quatre éléments, ce qui est une complexité de O (n) .

Sélection

Contrairement au tri à bulles , au lieu de remonter la valeur la plus élevée, le tri par sélection sélectionne la valeur la plus basse pour l'échanger vers les premières positions. Mais, comme il nécessite de comparer chaque élément au reste de la collection, il a également une complexité de O (n²) .

Insertion

Contrairement aux tris de bulles et de sélection , le tri par insertion insère l'élément dans sa position correcte. Mais, comme les types précédents, cela nécessite également de comparer chaque élément au reste de la collection, par conséquent, il a une complexité moyenne au pire des cas de O (n²) . Comme le tri à bulles , s'il ne reste qu'un seul élément à trier, il ne nécessite qu'un seul cycle de comparaisons pour insérer l'élément dans sa position correcte. Autrement dit, il a la meilleure complexité des cas de O (n) .

Structures de données

Tableaux

Comme il suffit d'une seule étape pour accéder à un élément d'un tableau via son index ou pour ajouter / supprimer un élément à la fin d'un tableau, la complexité pour accéder , pousser ou sauter une valeur dans un tableau est O (1) . Alors que la recherche linéaire dans un tableau via son index, comme vu précédemment, a une complexité de O (n) .

De plus, comme un changement ou unshift d'une valeur en provenance ou à l'avant d'un tableau nécessite réindexation chaque élément qui le suit ( par exemple la suppression d' un élément à l' index 0 nécessite élément réétiquetage à l' index 1 comme index 0, et ainsi de suite), ils ont une complexité de O (n) . Le réétiquetage est effectué du début à la fin du tableau.

Clé - Objets associés à des valeurs

L'accès , l' insertion ou la suppression d' une valeur à l'aide d'une clé est instantané, et donc, ils ont une complexité de O (1) . La recherche dans chaque «boîte de dépôt» pour un article spécifique en utilisant chaque clé disponible est essentiellement une recherche linéaire . Et donc, il a une complexité de O (n) .

Conclusion

La complexité est plus qu'un simple sujet pour discuter des algorithmes et des structures de données établis. S'il est utilisé à bon escient, il peut être un outil utile pour évaluer l'efficacité du travail que vous faites et le code que vous créez pour résoudre vos problèmes.

Référence:

//www.udemy.com/js-algorithms-and-data-structures-masterclass/