Ce qu'ils n'enseignent généralement pas dans les bootcamps. Implémentations pratiques d'algorithmes courants en JavaScript idiomatique.

Je vais vous présenter comment penser les algorithmes, comment les estimer, les optimiser, les récursions et tout ce que vous devez savoir en tant qu'ingénieur JavaScript crédible . Des choses que j'aurais aimé savoir plus tôt dans ma carrière lors des entretiens.

Détendez-vous, prenez votre temps et profitez-en.

Qu'est-ce qu'un algorithme?

• C'est un ensemble d'instructions pour résoudre un problème.
• En tant qu'ingénieur, c'est votre travail / objectif de résoudre les problèmes
• Lors de la résolution de problèmes, vous identifiez des modèles / techniques qui sont plus efficaces / performants
• Rappelez-vous qu'il existe de nombreuses façons de résoudre un seul problème, mais laquelle est la plus rapide lorsque la quantité de données d'entrée à traiter augmente?

• La complexité temporelle correspond au nombre d'opérations primitives exécutées dans un algorithme au fur et à mesure que les données lui sont transmises
• Cela aide à raisonner sur la vitesse d'un algorithme
  - C'est une approximation du temps qu'il faut pour exécuter un algorithme à mesure que les données d'entrée augmentent
  - C'est une approximation car vous ne pouvez pas prédire exactement combien de temps un algorithme prendra pour s'exécuter sur tous les types possibles de architectures de machines / environnements / configurations matérielles / etc
  donc , au lieu d'utiliser secondes ou millisecondes, un facteur de croissance est utilisé pour indiquer à quel point un algorithme tend à se développer comme vous nourrir des données.
• Pour résumer, la complexité temporelle est le nombre d' opérations primitives exécutées pour résoudre un problème à mesure que l'entrée augmente et dans le pire des cas .
• Pensez au coût des opérations effectuées. Plus un algorithme est rapide, plus il peut traiter de données dans un délai raisonnable.

• La complexité de l'espace est la quantité de mémoire utilisée par rapport à la taille d'entrée lors de l'exécution d'un algorithme

Disons que vous avez une liste de fournisseurs VPN sur une plate-forme. Vous voulez résoudre les problèmes les plus chers et les moins chers. N'oubliez pas que les fournisseurs sont ajoutés chaque jour, de sorte que la liste ne cesse de s'allonger.

const vpnProviders = [
 { name: 'totoVpn', price: 234 },
 { name: 'titoVpn', price: 321 },
 { name: 'tatoVpn', price: 99 },
 { name: 'tutoVpn', price: 54 },
 ...
];

Au fur et à mesure que vous parcourez la liste, vous gardez une trace du prix le plus élevé et le plus bas par itération.

Voyons une représentation de lors de la recherche du prix le plus cher:

       |  234  |  321  |  99  |  54  |
--------------------------------------
  234  |  --   |  321  |  234 |  234 |
--------------------------------------
  321  |  321  |  --   |  321 |  321 |
--------------------------------------
   99  |  234  |  321  |  --  |  99  |
--------------------------------------
   54  |  234  |  321  |  99  |  --  |

 # of providers (n)  |   4  |  11  |  100     |  2000      |
------------------------------------------------------------
 # of operations     |  16  |  121 |  10,000  |  4,000,000 |

• à mesure que le nombre n de fournisseurs augmente, le nombre d'opérations augmente de la puissance de deux (4², 11², 100² opérations).
• Donc, fondamentalement, plus vos données augmentent, plus le travail sera énorme

      |  234  |  321   |  ...  |  99  |  54  |
----------------------------------------------
max?  |  234  |  321   |  ...  |  321 |  321 |

      |  234  |  321   |  ...  |  99  |  54  |
- --------------------------------------------
min?  |  234   |  234  |  ...  |  99  |  54  |

• Chaque élément de la liste n'est regardé qu'une seule fois dans l'itération de la boucle et il est stocké s'il remplit la condition (est max, est min)
• ici la complexité temporelle est linéaire ( ici, 2n) en raison des deux boucles distinctes qui regardent tous les éléments une fois
• le nombre d'opérations à effectuer est le double du nombre d'éléments ou tout simplement, à mesure que les données augmentent, le travail augmente de 2.

# of providers (n)  |   4  |  11  |  100  |  2000  |
----------------------------------------------------
 # of operations    |   8  |   22 |  200  |  4,000 |

const vpnProviders = [
 { name: 'tutoVpn', price: 54 },
 { name: 'tatoVpn', price: 99 },
 { name: 'totoVpn', price: 234 },
 { name: 'titoVpn', price: 321 },
 ...
];

• pas besoin de boucles, juste 2 opérations, définissez la première valeur comme minimum et définissez la dernière valeur comme maximum
• donc la complexité temporelle de l'algorithme a une croissance constante car peu importe le nombre n d'éléments, le nombre d'opérations reste le même

# of providers (n)  |   4  |  11  |  100  |  2000  |
----------------------------------------------------
 # of operations    |   2 |    2  |    2  |   2    |

• La croissance de la complexité temporelle est représentée par la grande notation O
• jusqu'ici, nous avons vu:
  - Complexité temporelle quadratique représentée par O (n²)
  - Complexité temporelle linéaire représentée par O (n)
  - Complexité temporelle constante représentée par O (1)
• Parce que la complexité de la tme est une approximation, les nombres insignifiants sont supprimés donc une complexité de temps de 2n est juste O (n) et non O (2n)
• Les facteurs sont supprimés:
  - 5n est O (n) [prononcé "o de n"]
  - 24n² est O (n²) [prononcé "o de n carré"]
• voici une représentation graphique de la croissance:

• connaître la complexité du temps vous aide à comprendre les limites d'un algorithme en termes de quantité de données qu'il peut supporter avant qu'il ne prenne un million d'années pour se terminer
• Cela aide également à faire des compromis sur le choix d'un algorithme par rapport aux autres en fonction de certaines conditions
• la notion d' exactitude algorithmique concerne votre choix d'algorithme, est-ce la solution la plus optimale / correcte?

• remarquez avec une complexité temporelle logarithmique (O (log n)) , plus vous alimentez l'algorithme de données, moins il a de travail à faire, mais remarquez également qu'au début cela prend plus de temps qu'une complexité temporelle quadratique
• donc de très performant à extrêmement lent, vous avez:
  - Complexité temporelle constante représentée par O (1)
  - Complexité temporelle l ogarithmique représentée par O (log n)
  - Complexité temporelle linéaire représentée par O (n)
  - Complexité temporelle quadratique représentée par O (n²)
  - Complexité temporelle C ubique représentée par O (n³)
  - Complexité temporelle exponentielle représentée par O (k)