Supposons que nous ayons besoin de savoir si l’adresse e-mail « demensdeum@gmail.com » est incluse dans la liste des adresses e-mail autorisées pour la réception de lettres. .
Parcourons toute la liste du premier au dernier élément, en vérifiant si l’élément est égal à l’adresse spécifiée – Implémentons un algorithme de recherche linéaire. Mais cela prendra beaucoup de temps, n’est-ce pas ?
Pour répondre à cette question, utilisez la notation « Complexité temporelle des algorithmes », « O ». Le temps de fonctionnement de la recherche linéaire dans le pire des cas est égal au nième nombre d’éléments du tableau, écrivons cela en notation « O » – Sur). Ensuite, nous devons expliquer que pour tout algorithme connu, il existe trois indicateurs de performance : temps d’exécution dans le meilleur des cas, le pire des cas et la moyenne. Par exemple, l’adresse mail « demensdeum@gmail.com » est dans le premier index du tableau, elle sera alors trouvée dans la première étape de l’algorithme, il s’ensuit que le temps d’exécution est au mieux – O(1); et si à la fin de la liste, alors c’est le pire des cas – O(n)
Mais qu’en est-il des détails de la mise en œuvre logicielle et des performances matérielles ? Ils devraient influencer Big O ? Maintenant, respirez et imaginez que le calcul de la complexité temporelle soit calculé pour une machine idéale abstraite, dans laquelle il n’y a que cet algorithme et rien d’autre.
Algorithme
Ok, il s’avère que la recherche linéaire est assez lente, essayons d’utiliser la recherche binaire. Pour commencer, il convient de préciser que nous ne travaillerons pas avec des données binaires ; ce nom a été donné à cette méthode en raison des particularités de son travail. Initialement, nous trions le tableau en ordre lexicographique, puis l’algorithme prend la plage de l’ensemble du tableau, obtient l’élément central de la plage, le compare lexicographiquement, et en fonction du résultat de la comparaison, décide quelle plage utiliser pour poursuivre la recherche – la moitié supérieure du courant ou la moitié inférieure. Autrement dit, à chaque étape de recherche, une décision est prise parmi deux options possibles : logique binaire. Cette étape est répétée jusqu’à ce que le mot soit trouvé ou non (l’intersection des indices inférieur et supérieur de la plage se produit).
Performances de cet algorithme – le meilleur des cas est lorsqu’un élément est immédiatement trouvé au milieu du tableau O(1), le pire des cas d’énumération est O(log n)
Pièges
Lors de l’implémentation de la recherche binaire, j’ai non seulement rencontré le problème intéressant du manque de standardisation de la comparaison lexicographique dans les bibliothèques de langages de programmation, mais j’ai même découvert l’absence d’un standard unifié pour l’implémentation localeCompare dans JavaScript. La norme ECMAScript permet différentes implémentations de cette fonction, c’est pourquoi lors du tri à l’aide de localeCompare, des résultats complètement différents peuvent être observés sur différents moteurs JavaScript.
Par conséquent, pour que l’algorithme fonctionne correctement, il faut trier et utiliser uniquement le même algorithme de comparaison lexicographique, sinon rien ne fonctionnera. Co-mais si, par exemple, vous essayez de trier un tableau dans Scala et d’effectuer une recherche à l’aide de nodejs, sans implémenter votre propre tri/tri d’une implémentation, alors rien ne vous attend sauf une déception humaine.
Sources
Qu’est-ce que la comparaison lexicographique et que représente-t-elle ?
Почему для вычисления сложности алгоритмов используется log N вместо lb N?
Двоичный поиск
Знай сложности алгоритмов
https://stackoverflow.com/questions/52941016/sorting-in-localecompare-in-javascript
Code source
https://gitlab.com/demensdeum/algorithms
