Top Algorithmen und Datenstrukturen, die Sie wirklich kennen müssen
Wenn Sie Software-Ingenieur werden wollen, aber nicht wissen, wo Sie anfangen sollen, ersparen wir Ihnen die Spannung: Es sind Algorithmen und Datenstrukturen.
Wenn Sie diese Säulen der Programmierung einmal verstanden haben, werden Sie sie überall sehen. Und je mehr Algorithmen und Datenstrukturen Sie lernen, desto mehr werden sie als Treibstoff für Ihre Karriere als Software-Ingenieur dienen.
Zu Beginn wollen wir uns zunächst mit Suchen und Sortieren beschäftigen, zwei Klassen von Algorithmen, ohne die Sie nicht leben können. Dann wollen wir einen kurzen Überblick über den Rest der Landschaft geben, die Bäume, Graphen, dynamische Programmierung und vieles mehr umfasst.
Grob gesagt gibt es zwei Kategorien von Suchalgorithmen, die Sie sofort kennen müssen: lineare und binäre. Depth First Search (DFS) und Breadth First Search (BFS) sind ebenfalls sehr wichtig, aber die heben wir uns für den Abschnitt über Graphentraversal auf.
Lineare Suche
Die linearen und binären Algorithmen werden so genannt, um zu beschreiben, wie lange (Zeitkomplexität) eine Suche auf der Grundlage der Größe der Eingabe, die durchsucht wird, dauern wird.
Beim linearen Suchalgorithmus müsste man beispielsweise bei 100 zu durchsuchenden Elementen im schlimmsten Fall jedes Element der Eingabe durchsehen, bevor man auf den gewünschten Wert stößt. Der Algorithmus wird als linear bezeichnet, weil die für die Suche benötigte Zeit genau mit der Anzahl der Elemente in der Suche korreliert (100 Elemente/Eingabe = 100 Prüfungen/Komplexität)
Kurz gesagt, linear = einfach (der Algorithmus ist nicht clever). Ein Beispiel: Stellen Sie sich vor, Sie versuchen, Ihren Freund Lin in einer Reihe von Menschen zu finden, die in keiner bestimmten Reihenfolge stehen. Sie wissen bereits, wie Lin aussieht, also müssen Sie einfach jede Person der Reihe nach ansehen, bis Sie Lin erkennen oder nicht erkennen. Das war’s. Dabei folgst du dem linearen Suchalgorithmus
Binärsuche
Der Name Binärsuche kommt daher, dass das Wort binär „von oder in Bezug auf zwei Dinge“ bedeutet und der Algorithmus funktioniert, indem er die Eingabe in zwei Teile aufteilt, bis er das gesuchte Element findet. Die eine Hälfte enthält das gesuchte Element, die andere nicht. Der Prozess wird so lange fortgesetzt, bis die Stelle, an der die Eingabe geteilt wurde, zum gesuchten Element wird. Die binäre Suche ist im Grunde nur ein sehr disziplinierter Ansatz für den Eliminierungsprozess. Sie ist schneller als die lineare Suche, aber sie funktioniert nur bei geordneten Sequenzen.
Ein Beispiel soll dies verdeutlichen. Nehmen wir an, du versuchst, deinen Freund Bin (der 1,70 m groß ist) in einer Reihe von Menschen zu finden, die nach ihrer Größe von links nach rechts geordnet sind, vom Kleinsten zum Größten. Die Schlange ist sehr lang, und du hast keine Zeit, sie einzeln durchzugehen und die Größe aller mit der von Bin zu vergleichen. Was können Sie tun?
Binäre Suche eingeben. Sie wählen die Person in der Mitte der Reihe aus und messen ihre Größe. Sie ist 1,70 m groß. Sie wissen also sofort, dass diese Person, ebenso wie alle anderen rechts von ihr, nicht Bin ist. Nun, da du dein Problem halbiert hast, wendest du deine Aufmerksamkeit dem Rest der Reihe zu und wählst wieder die Person in der Mitte. Sie ist 1,70 m groß. Sie können also diese Person und alle Personen links von ihr ausschließen, wodurch sich das Problem erneut halbiert. Und so weiter. Nach nur fünf oder sechs dieser Teilungen haben Sie Bin in einem Bruchteil der Zeit, die Sie für die Suche nach Lin gebraucht haben, schnell gefunden. Dabei sind Sie dem binären Suchalgorithmus gefolgt.
Sortieren
Das Ordnen, auch Sortieren genannt, von Listen ist eine der häufigsten Programmieraufgaben, die Sie als Entwickler erledigen. Hier sehen wir uns zwei der nützlichsten Sortieralgorithmen an: MergeSort und QuickSort.
MergeSort
Angenommen, Sie müssen aus einer ungeordneten Gruppe eine geordnete Reihe von Personen erstellen, statt wie im obigen Beispiel eine geordnete Reihe von Personen zu finden. Da Sie nicht viel Zeit haben, lassen Sie sich eine Strategie einfallen, um die Sache zu beschleunigen.
Zunächst lassen Sie die Gruppe von Menschen, die alle zusammengedrängt sind, in zwei Gruppen aufteilen. Dann teilen Sie jede der beiden Gruppen wieder in zwei und so weiter, bis Sie nur noch mit Einzelpersonen zu tun haben. Dann fangen Sie an, die Personen zu Paaren zusammenzufassen, und lassen den größeren der beiden in jedem Paar rechts von dem anderen stehen.
Als Nächstes fasst man die geordneten Paare zu geordneten Vierergruppen zusammen, dann die geordneten Vierergruppen zu geordneten Achtergruppen, und so weiter. Schließlich stellen Sie fest, dass Sie eine vollständige, in der Höhe geordnete Reihe von Menschen haben, genau wie die, die Sie oben gesehen haben. Ohne es zu wissen, haben Sie den MergeSort-Algorithmus angewendet, um Ihre Aufgabe zu erfüllen.
QuickSort
QuickSort ist ein bisschen zu komplex, um es sich einfach vorstellen zu können, also gehen wir etwas näher an den Code heran. Stellen Sie sich vor, Sie haben eine ungeordnete Liste oder ein Array mit acht Zahlen, die Sie ordnen wollen.
4 2 13 6 15 12 7 9
Sie könnten MergeSort verwenden, aber Sie haben gehört, dass QuickSort im Allgemeinen schneller ist, also entscheiden Sie sich, es zu versuchen. Der erste Schritt besteht darin, eine Zahl in der Liste zu wählen, die als Pivot bezeichnet wird. Die Wahl der richtigen Pivot-Nummer ist ausschlaggebend dafür, wie schnell QuickSort arbeitet, und es gibt fertige Formeln für die Wahl guter Pivots. Aber für den Moment halten wir es einfach und nehmen die letzte Zahl im Array als Pivot-Nummer: 9.
4 2 13 6 15 12 7 9
Um den nächsten Schritt einfacher zu machen, erstellen wir ein Trennzeichen am Anfang des Arrays und stellen es mit dem Pfund-Zeichen dar.
# 4 2 13 6 15 12 7 9
Wir gehen von links nach rechts durch unser Array und versuchen, jede Zahl, die kleiner als der Drehpunkt (9) ist, links vom Trennzeichen und jede Zahl, die größer (oder gleich) als der Drehpunkt ist, rechts vom Trennzeichen anzuordnen. Wir beginnen mit der ersten Zahl in unserem Array: 4. Um sie links vom Trennzeichen zu platzieren, verschieben wir das Trennzeichen einfach um ein Element nach oben:
4 # 2 13 6 15 12 7 9
Das Gleiche machen wir mit der nächsten Zahl: 2.
4 2 # 13 6 15 12 7 9
Aber dann kommen wir zur 13, die größer ist als die Pivot-Zahl 9 und sich bereits rechts vom Trennzeichen befindet. Also lassen wir es dabei bewenden. Als nächstes kommen wir zu 6, die links vom Trennzeichen stehen muss. Also tauschen wir sie zuerst mit der 13, um sie in die richtige Position zu bringen:
4 2 # 6 13 15 12 7 9
Dann schieben wir das Trennzeichen an ihr vorbei:
4 2 6 # 13 15 12 7 9
Als Nächstes kommt die 15, die bereits rechts vom Trennzeichen liegt, also lassen wir sie in Ruhe. Dann haben wir 12. Das ist das Gleiche. Aber 7, unsere letzte Zahl vor dem Erreichen des Drehpunkts, braucht die gleiche Art von Hilfe, um sich zu bewegen wie 6. Also tauschen wir die 7 mit der 13, um sie in die richtige Position zu bringen:
4 2 6 # 7 15 12 13 9
Dann schieben wir das Trennzeichen noch einmal an ihr vorbei:
4 2 6 7 # 15 12 13 9
Schließlich kommen wir zu unserer Pivot-Zahl: 9. Nach der gleichen Logik wie oben tauschen wir 15 mit 9, um die Pivot-Zahl an die richtige Stelle zu bringen:
4 2 6 7 # 9 12 13 15
Da alle Zahlen links von 9 nun kleiner als 9 und alle Zahlen rechts von 9 größer als 9 sind, ist unser erster QuickSort-Zyklus abgeschlossen. Als Nächstes behandeln wir jeden Satz von vier Zahlen auf beiden Seiten des Trennzeichens als neues Array, auf das wir QuickSort anwenden. Wir ersparen Ihnen die Details, aber die nächste Runde wird uns vier Zahlenpaare liefern, auf die wir unsere letzte Runde QuickSort anwenden können. Das Endergebnis ist die folgende geordnete Liste, deren Erstellung weniger Zeit in Anspruch genommen hat, als dies bei der einfacheren MergeSort der Fall gewesen wäre:
2 4 6 7 9 12 13 15
Sortieralgorithmus-Spickzettel
Dies sind die gebräuchlichsten Sortieralgorithmen mit einigen Empfehlungen, wann man sie verwenden sollte. Verinnerlichen Sie diese! Sie werden überall verwendet!
Heap sort: Wenn Sie keine stabile Sortierung benötigen und Ihnen die Leistung im schlimmsten Fall wichtiger ist als die Leistung im durchschnittlichen Fall. Sie ist garantiert O(N log N) und verbraucht O(1) Hilfsplatz, was bedeutet, dass Ihnen bei sehr großen Eingaben nicht unerwartet der Heap- oder Stack-Platz ausgeht.
Introsort: Dies ist eine schnelle Sortierung, die nach einer bestimmten Rekursionstiefe auf eine Heap-Sortierung umschaltet, um den schlimmsten Fall von O(N²) zu umgehen. Sie ist fast immer besser als eine einfache alte Quick-Sortierung, da man den durchschnittlichen Fall einer Quick-Sortierung mit garantierter O(N log N) Leistung erhält. Der einzige Grund, stattdessen eine Heap-Sortierung zu verwenden, ist wahrscheinlich in stark speicherbeschränkten Systemen, wo O(log N) Stackspace praktisch signifikant ist.
Einfügungssortierung: Wenn N garantiert klein ist, auch als Basisfall einer Schnellsortierung oder Merge-Sortierung. Dies ist zwar O(N²), hat aber eine sehr kleine Konstante und ist eine stabile Sortierung.
Bubble Sort, Selection Sort: Wenn Sie etwas Schnelles und Schmutziges machen und aus irgendeinem Grund nicht einfach den Sortieralgorithmus der Standardbibliothek verwenden können. Der einzige Vorteil gegenüber der Einfügesortierung ist, dass sie etwas einfacher zu implementieren ist.
Schnelle Sortierung: Wenn Sie keine stabile Sortierung benötigen und die Leistung im durchschnittlichen Fall wichtiger ist als die Leistung im schlimmsten Fall. Eine schnelle Sortierung ist im Durchschnitt O(N log N), im schlimmsten Fall O(N²). Eine gute Implementierung verwendet O(log N) Hilfsspeicher in Form von Stapelplatz für Rekursionen.
Merge Sort: Wenn Sie eine stabile O(N log N)-Sortierung benötigen, ist dies so ziemlich die einzige Option. Die einzigen Nachteile sind, dass sie O(N)-Hilfsraum verbraucht und eine etwas größere Konstante als eine schnelle Sortierung hat. Es gibt einige In-Place-Merge-Sortierungen, aber AFAIK sind sie alle entweder nicht stabil oder schlechter als O(N log N). Selbst die O(N log N) in-place Sortierungen haben eine so viel größere Konstante als die einfache alte Merge-Sortierung, dass sie eher theoretische Kuriositäten als nützliche Algorithmen sind.