Angenommen, wir müssen herausfinden, ob die E-Mail-Adresse „demensdeum@gmail.com“ in der Liste der zulässigen E-Mail-Adressen für den Empfang von Briefen enthalten ist .
Lassen Sie uns die gesamte Liste vom ersten bis zum letzten Element durchgehen und prüfen, ob das Element mit der angegebenen Adresse übereinstimmt – Lassen Sie uns einen linearen Suchalgorithmus implementieren. Aber das wird lange dauern, oder nicht?
Um diese Frage zu beantworten, verwenden Sie die „Zeitkomplexität von Algorithmen“, „O“-Notation. Die Betriebszeit der linearen Suche entspricht im schlimmsten Fall der n-ten Anzahl von Array-Elementen. Schreiben wir dies in „O“-Notation – An). Als nächstes müssen wir erklären, dass es für jeden bekannten Algorithmus drei Leistungsindikatoren gibt: Best-Case-, Worst-Case- und Average-Case-Ausführungszeiten. Befindet sich beispielsweise die E-Mail-Adresse „demensdeum@gmail.com“ im ersten Index des Arrays, wird sie im ersten Schritt von gefunden Für den Algorithmus folgt daraus, dass die Ausführungszeit bestenfalls – O(1); und wenn am Ende der Liste, dann ist dies der schlimmste Fall – O(n)
Aber was ist mit den Details der Software-Implementierung und der Hardware-Leistung? Sie sollten einen großen Einfluss auf das O haben? Atmen Sie nun ein und stellen Sie sich vor, dass die Berechnung der Zeitkomplexität für eine abstrakte ideale Maschine berechnet wird, in der es nur diesen Algorithmus und sonst nichts gibt.
Algorithmus
Okay, es stellt sich heraus, dass die lineare Suche ziemlich langsam ist. Versuchen wir es mit der binären Suche. Zunächst sollte klargestellt werden, dass wir nicht mit Binärdaten arbeiten; dieser Name wurde dieser Methode aufgrund der Besonderheiten ihrer Arbeit gegeben. Zunächst sortieren wir das Array nach lexikografische Reihenfolge, dann nimmt der Algorithmus den Bereich des gesamten Arrays, ruft das mittlere Element des Bereichs ab und vergleicht es lexikographisch und abhängig vom Ergebnis des Vergleichs entscheidet, welcher Bereich für die weitere Suche verwendet werden soll – die obere Hälfte des Stroms oder die untere. Das heißt, bei jedem Suchschritt wird eine Entscheidung aus zwei möglichen – Binäre Logik. Dieser Schritt wird wiederholt, bis entweder das Wort gefunden wird oder nicht (der Schnittpunkt des unteren und oberen Index des Bereichs tritt auf).
Leistung dieses Algorithmus – Der beste Fall ist, wenn ein Element sofort in der Mitte des Arrays O(1) gefunden wird, der schlechteste Fall der Aufzählung ist O(log n)
Fallstricke
Bei der Implementierung der binären Suche bin ich nicht nur auf das interessante Problem der fehlenden Standardisierung des lexikografischen Vergleichs in Programmiersprachenbibliotheken gestoßen, sondern habe sogar festgestellt, dass es keinen einheitlichen Standard für die Implementierung gibt localeCompare innerhalb von JavaScript. Der ECMAScript-Standard erlaubt unterschiedliche Implementierungen dieser Funktion, weshalb beim Sortieren mit localeCompare auf verschiedenen JavaScript-Engines völlig unterschiedliche Ergebnisse beobachtet werden können.
Damit der Algorithmus korrekt funktioniert, ist es notwendig, nur denselben lexikografischen Vergleichsalgorithmus zu sortieren und zu verwenden, andernfalls funktioniert nichts. Co-aber wenn Sie beispielsweise versuchen, ein Array in Scala zu sortieren und mit NodeJS zu suchen, ohne Ihre eigene Sortierung/Sortierung einer Implementierung zu implementieren, dann erwartet Sie nichts außer Enttäuschung über die Menschheit.
Quellen
Was ist ein lexikografischer Vergleich und was stellt er dar?
Почему для вычисления сложности алгоритмов используется log N вместо lb N?
Двоичный поиск
Знай сложности алгоритмов
https://stackoverflow.com/questions/52941016/sorting-in-localecompare-in-javascript
Quellcode
https://gitlab.com/demensdeum/algorithms
