Im Leben von Programmierern sind Algorithmen und Datenstrukturen das wichtigste Thema, wenn sie in die Programmierwelt gehen und etwas Geld verdienen wollen. Heute werden wir sehen, was sie tun und wo sie mit einfachsten Beispielen verwendet werden. Diese Liste wird unter Berücksichtigung ihrer Verwendung in der Wettbewerbsprogrammierung und der aktuellen Entwicklungspraktiken erstellt.

Sortieralgorithmen

Sortierung ist das am stärksten untersuchte Konzept in der Informatik. Die Idee ist, die Elemente einer Liste in einer bestimmten Reihenfolge anzuordnen. Obwohl jede wichtige Programmiersprache über integrierte Sortierbibliotheken verfügt, ist dies praktisch, wenn Sie wissen, wie sie funktionieren. Je nach Anforderung können Sie eines davon verwenden.

• Sortierung zusammenführen
• Schnellsortierung
• Bucket-Sortierung
• Heap-Sortierung
• Zählsortierung

Noch wichtiger ist, dass man weiß, wann und wo man sie verwendet. Einige Beispiele für die direkte Anwendung von Sortiertechniken sind:

• Sortierung nach Preis, Beliebtheit usw. auf E-Commerce-Websites

Suchalgorithmen

Binäre Suche (in linearen Datenstrukturen)

Die binäre Suche wird verwendet, um eine sehr effiziente Suche nach sortierten Datensätzen durchzuführen. Die Zeitkomplexität ist O (log2N). Die Idee ist, den Teil der Liste, der das Element enthalten könnte, wiederholt in zwei Hälften zu teilen, bis wir es auf ein mögliches Element eingrenzen. Einige Anwendungen sind:

• Wenn Sie in einer sortierten Liste von Songs nach einem Songnamen suchen, führt es eine binäre Suche und einen String-Matching durch, um die Ergebnisse schnell zurückzugeben.
• Wird zum Debuggen in Git über git bisect verwendet

Tiefe / Breite Erste Suche (in Diagrammdatenstrukturen)

DFS und BFS sind Baum- / Diagrammdurchlauf- und Suchdatenstrukturen. Wir würden nicht tief in die Funktionsweise von DFS / BFS eingehen, werden aber anhand der folgenden Animation sehen, wie sie sich unterscheiden.

Anwendungen:

• Wird von Suchmaschinen für das Webcrawling verwendet
• Wird in der künstlichen Intelligenz verwendet, um Bots zu erstellen, zum Beispiel einen Schachbot
• Kürzesten Weg zwischen zwei Städten in einer Karte finden und viele andere solche Anwendungen

Hashing

Hash-Lookup ist derzeit die am weitesten verbreitete Technik, um geeignete Daten nach Schlüssel oder ID zu finden. Wir greifen auf Daten über ihren Index zu. Früher haben wir uns auf Sortierung + binäre Suche verlassen, um nach Index zu suchen, während wir jetzt Hashing verwenden.

Die Datenstruktur wird als Hash-Map oder Hash-Tabelle oder Wörterbuch bezeichnet, das Schlüssel effizient auf Werte abbildet. Wir können Wertesuchen mit Schlüsseln durchführen. Die Idee ist, eine geeignete Hash-Funktion zu verwenden, die die key -> -Wertzuordnung ausführt. Die Auswahl einer guten Hash-Funktion hängt vom Szenario ab.

Anwendungen:

• In Routern zum Speichern der IP-Adresse -> Pfadpaar für Routingmechanismen
• Um zu prüfen, ob ein Wert bereits in einer Liste vorhanden ist. Lineare Suche wäre teuer. Wir können auch Set data structure für diese Operation verwenden.

Dynamische Programmierung

Dynamische Programmierung (DP) ist eine Methode zur Lösung eines komplexen Problems, indem es in einfachere Teilprobleme zerlegt wird. Wir lösen die Teilprobleme, erinnern uns an ihre Ergebnisse und machen uns auf den Weg, das komplexe Problem schnell zu lösen.

*schreibt „1+1+1+1+1+1+1+1 =“ auf einem Blatt Papier* Was ist das gleich?
* zählen * Acht!
* schreibt eine weitere „1+“ auf der linken Seite * Was ist damit?
*schnell* Neun!
Woher wusstest du, dass es so schnell neun war?
Du hast gerade noch einen hinzugefügt, damit du nicht nachzählen musst, weil du dich daran erinnerst, dass es acht waren! Dynamische Programmierung ist nur eine ausgefallene Art zu sagen, dass man sich an Dinge erinnert, um später Zeit zu sparen.

Anwendungen:

• Es gibt viele DP-Algorithmen und Anwendungen, aber ich würde einen nennen und dich umhauen, Duckworth-Lewis-Methode im Cricket.

Potenzierung durch Quadrieren

Angenommen, Sie möchten 232 berechnen. Normalerweise würden wir 32 Mal iterieren und das Ergebnis finden. Was wäre, wenn ich Ihnen sagen würde, dass dies in 5 Iterationen möglich ist?

Die Potenzierung durch Quadrieren oder binäre Potenzierung ist eine allgemeine Methode zur schnellen Berechnung großer positiver ganzzahliger Potenzen einer Zahl in O (log2N). Darüber hinaus wird die Methode auch zur Berechnung von Potenzen von Polynomen und quadratischen Matrizen verwendet.

Anwendung:

• Die Berechnung großer Potenzen einer Zahl ist bei der RSA-Verschlüsselung meist erforderlich. RSA verwendet auch modulare Arithmetik zusammen mit binärer Potenzierung.

String Matching und Parsing

Pattern Matching/Suche ist eines der wichtigsten Probleme in der Informatik. Es wurde viel zu diesem Thema geforscht, aber wir werden nur zwei grundlegende Notwendigkeiten für jeden Programmierer anführen.

KMP-Algorithmus (String Matching)

Der Knuth-Morris-Pratt-Algorithmus wird in Fällen verwendet, in denen wir ein kurzes Muster in einer langen Zeichenfolge abgleichen müssen. Wenn wir beispielsweise ein Schlüsselwort in einem Dokument Strg + F drücken, führen wir einen Mustervergleich im gesamten Dokument durch.

Regulärer Ausdruck (String-Parsing)

Oft müssen wir einen String validieren, indem wir eine vordefinierte Einschränkung analysieren. Es wird in der Webentwicklung häufig zum Parsen und Abgleichen von URLs verwendet.

Primalitätstestalgorithmen

Es gibt deterministische und probabilistische Methoden, um zu bestimmen, ob eine gegebene Zahl Primzahl ist oder nicht. Wir werden sowohl deterministische als auch probabilistische (nichtdeterministische) Wege sehen.

Sieb des Eratosthenes (deterministisch)

Wenn wir eine bestimmte Grenze für den Zahlenbereich haben, sagen wir, bestimmen Sie alle Primzahlen im Bereich von 100 bis 1000, dann ist Sieb ein Weg zu gehen. Die Länge des Bereichs ist ein entscheidender Faktor, da wir je nach Bereich eine bestimmte Speichermenge zuweisen müssen.

Testen Sie für eine beliebige Zahl n inkrementell bis zu sqrt(n) (deterministisch)

Falls Sie nach wenigen Zahlen suchen möchten, die nur spärlich über einen großen Bereich verteilt sind (z. B. 1 bis 1012), können Sie nicht genügend Speicher zuweisen. Sie können nach jeder Zahl n suchen, indem Sie nur bis zu sqrt(n) durchlaufen und eine Teilbarkeitsprüfung für n durchführen.

Fermat–Primalitätstest und Miller-Rabin-Primalitätstest (beide sind nicht deterministisch)

Beide sind Zusammensetzungstests. Wenn sich herausstellt, dass eine Zahl zusammengesetzt ist, ist sie sicher keine Primzahl. Miller-Rabin ist anspruchsvoller als Fermat. Tatsächlich hat Miller-Rabin auch eine deterministische Variante, aber dann ist es ein Handelsspiel zwischen Zeitkomplexität und Genauigkeit des Algorithmus.

Anwendung:

• Die wichtigste Verwendung von Primzahlen ist in der Kryptographie. Genauer gesagt werden sie bei der Ver- und Entschlüsselung im RSA-Algorithmus verwendet, der die allererste Implementierung von Kryptosystemen mit öffentlichem Schlüssel war
• Eine weitere Verwendung findet sich in Hash-Funktionen, die in Hash-Tabellen verwendet werden