Die zehn besten Programmieralgorithmen helfen Programmierern auf dem Weg zum Meister

Algorithmus 1: Schnellsortieralgorithmus Schnellsortierung ist ein von Tony Hall entwickelter Sortieralgorithmus. Im Durchschnitt erfordert das Sortieren von n Elementen O(n log n) Vergleiche. Im schlimmsten Fall sind O(n2)-Vergleiche erforderlich, aber diese Situation ist ungewöhnlich. Tatsächlich ist Quicksort häufig deutlich schneller als andere Ο(n log n)-Algorithmen, da seine innere Schleife auf den meisten Architekturen effizient implementiert werden kann. Schnellsortierung verwendet die Divide-and-Conquer-Strategie, um eine Sequenz (Liste) in zwei Unterreihen (Unterlisten) zu unterteilen. Algorithmusschritte: 1 Wählen Sie ein Element aus der Sequenz aus, das als „Pivot“ bezeichnet wird. 2 Ordnen Sie die Sequenz neu an, sodass alle Elemente, die kleiner als der Pivotwert sind, platziert werden vor der Basis, und alle Elemente, die größer als der Basiswert sind, werden hinter der Basis platziert (die gleiche Anzahl kann auf beiden Seiten platziert werden). Nachdem diese Partition beendet wurde, befindet sich die Basis in der Mitte der Sequenz. Dies wird als Partitionsvorgang bezeichnet. 3 Sortieren Sie das Subarray der Elemente, die kleiner als der Basiswert sind, und das Subarray der Elemente, die größer als der Basiswert sind, rekursiv. Der unterste Fall einer Rekursion liegt vor, wenn die Größe des Arrays Null oder Eins ist, das heißt, es wurde immer sortiert. Obwohl er ständig rekursiv ist, wird dieser Algorithmus immer beendet, da er in jeder Iteration mindestens ein Element an seine endgültige Position verschiebt. Algorithmus 2: Heap-Sortieralgorithmus Heapsort bezieht sich auf eine Methode, die unter Verwendung der Datenstruktur eines Heap-Sortieralgorithmus entwickelt wurde . Stapeln ist eine Struktur, die sich einem vollständigen Binärbaum annähert und gleichzeitig die Eigenschaften des Stapelns erfüllt: Das heißt, der Schlüsselwert oder Index eines untergeordneten Knotens ist immer kleiner (oder größer) als der seines übergeordneten Knotens. Die durchschnittliche zeitliche Komplexität der Heap-Sortierung beträgt Ο(nlogn). Algorithmusschritte: Erstellen Sie einen Heap H[0..n-1]Tauschen Sie den Kopf (Maximalwert) und das Ende des Heaps aus3. Reduzieren Sie die Größe des Heaps um 1 und rufen Sie shift_down(0) auf, um die oberen Daten des neuen Arrays an die entsprechende Position anzupassen4 Wiederholen Sie Schritt 2, bis die Größe des Heaps 1 ist Algorithmus 3: Sortierung zusammenführenZusammenführungssortierung (Zusammenführungssortierung, taiwanesische Übersetzung: Zusammenführungssortierung) ist ein effektiver Sortieralgorithmus, der auf Zusammenführungsoperationen basiert. Dieser Algorithmus ist eine sehr typische Anwendung der Divide-and-Conquer-Methode. Algorithmusschritte: 1. Beantragen Sie Platz, sodass seine Größe der Summe zweier sortierter Sequenzen entspricht. Dieser Platz wird zum Speichern der zusammengeführten Sequenz verwendet. 2 Definieren Sie zwei Zeiger, die Anfangspositionen sind die Anfangspositionen der beiden sortierten Sequenzen 3. Vergleichen Sie die Elemente, auf die die beiden Zeiger zeigen, wählen Sie das relativ kleine Element aus, legen Sie es in den Zusammenführungsraum und verschieben Sie es Zeiger auf die nächste Position 4. Wiederholen Sie Schritt 3, bis ein Zeiger das Ende der Sequenz erreicht 5. Kopieren Sie alle verbleibenden Elemente der anderen Sequenz direkt an das Ende der zusammengeführten Sequenz Algorithmus 4: Binärer Suchalgorithmus Der binäre Suchalgorithmus ist ein Suchalgorithmus zum Suchen eines bestimmten Elements in einem geordneten Array. Der Suchvorgang beginnt beim mittleren Element des Arrays. Wenn das mittlere Element das zu durchsuchende Element ist, endet der Suchvorgang, wenn ein bestimmtes Element größer oder kleiner als das mittlere Element ist Array, das größer oder kleiner als das mittlere Element ist, und beginnen Sie mit dem Vergleich vom mittleren Element aus, genau wie am Anfang. Wenn das Array in einem bestimmten Schritt leer ist, bedeutet dies, dass es nicht gefunden werden kann. Dieser Suchalgorithmus reduziert den Suchbereich bei jedem Vergleich um die Hälfte. Die halbe Suche reduziert den Suchbereich jedes Mal um die Hälfte und die zeitliche Komplexität beträgt Ο(logn). Algorithmus 5: BFPRT (Linearer Suchalgorithmus)Das durch den BFPRT-Algorithmus gelöste Problem ist sehr klassisch, nämlich die Auswahl des k-größten (k-kleinsten) Elements Durch geschickte Analyse kann BFPRT garantieren, dass die Zeitkomplexität im schlimmsten Fall immer noch linear ist. Die Idee dieses Algorithmus ähnelt der der schnellen Sortierung. Damit der Algorithmus im schlimmsten Fall immer noch eine Zeitkomplexität von o (n) erreicht, haben die fünf Algorithmusautoren eine exquisite Verarbeitung durchgeführt. Algorithmusschritte: 1. Teilen Sie n Elemente in Gruppen von 5 und teilen Sie sie in n/5 (Obergrenze) Gruppen auf. 2. Ermitteln Sie den Medianwert jeder Gruppe und sortieren Sie nach einer beliebigen Methode, z. B. Einfügungssortierung. 3. Rufen Sie den Auswahlalgorithmus rekursiv auf, um den Median aller Mediane im vorherigen Schritt zu ermitteln, setzen Sie ihn auf x und stellen Sie ihn bei einer geraden Anzahl von Medianen so ein, dass der kleinere ausgewählt wird die Mitte. 4. Teilen Sie das Array mit x, die Zahl kleiner oder gleich x sei k und die Zahl größer als x sei n-k. 5. Wenn i==k, gib x zurück; wenn iAbbruchbedingung: Wenn n=1, wird das kleine Element i zurückgegeben. Algorithmus 6: DFS (Depth-First Search) Depth-First-Search ist eine Art Suchalgorithmus. Es durchquert die Knoten des Baums entlang der Tiefe des Baums und durchsucht die Äste des Baums so tief wie möglich. Wenn alle Kanten des Knotens v erkundet wurden, wird die Suche zum Startknoten der Kante zurückverfolgt, an der der Knoten v gefunden wurde. Dieser Prozess wird fortgesetzt, bis alle vom Quellknoten aus erreichbaren Knoten erkannt wurden. Wenn noch unentdeckte Knoten vorhanden sind, wählen Sie einen davon als Quellknoten aus und wiederholen Sie den obigen Vorgang. Der gesamte Vorgang wird wiederholt, bis alle Knoten besucht sind. DFS ist eine blinde Suche. Die Tiefensuche ist ein klassischer Algorithmus in der Graphentheorie. Der Tiefensuchalgorithmus kann zum Generieren der entsprechenden topologischen Sortiertabelle des Zielgraphen verwendet werden verwandte Probleme der Graphentheorie, wie zum Beispiel Fragen zum maximalen Pfad und mehr. Heap-Datenstrukturen werden im Allgemeinen verwendet, um die Implementierung des DFS-Algorithmus zu unterstützen. Schritte des Tiefendurchquerungsdiagramms: 1. Besuchen Sie den Scheitelpunkt v. 2 Führen Sie eine Tiefendurchquerung des Diagramms durch Durchlaufen, bis alle Scheitelpunkte im Diagramm besucht sind, deren Pfade mit v verbunden sind; Priorität erneut. Traverse, bis alle Scheitelpunkte im Diagramm besucht wurden. Die obige Beschreibung kann relativ abstrakt sein: DFS beginnt bei v, nachdem es einen bestimmten Startscheitelpunkt v im Diagramm besucht hat, und besucht dann einen seiner angrenzenden Scheitelpunkte w1 Besuchen Sie ausgehend von w1 den Scheitelpunkt w2, der an w1 angrenzt, aber noch nicht besucht wurde. Beginnen Sie dann bei w2 und führen Sie ähnliche Besuche durch ... und fahren Sie auf diese Weise fort, bis Sie den Scheitelpunkt u erreichen, an dem alle angrenzenden Scheitelpunkte besucht wurden. Machen Sie dann einen Schritt zurück zu dem Scheitelpunkt, der gerade das letzte Mal besucht wurde, um zu sehen, ob es noch andere benachbarte Scheitelpunkte gibt, die noch nicht besucht wurden. Wenn dies der Fall ist, besuchen Sie diesen Scheitelpunkt und fahren Sie dann von diesem Scheitelpunkt aus fort, um einen Besuch ähnlich dem oben genannten durchzuführen. Wenn nicht, gehen Sie einen Schritt zurück und suchen Sie. Wiederholen Sie den obigen Vorgang, bis alle Eckpunkte im verbundenen Diagramm besucht wurden. Algorithmus 7: BFS (Breadth-First Search) Breadth-First-Search ist ein Graphsuchalgorithmus. Einfach ausgedrückt beginnt BFS am Wurzelknoten und durchläuft die Knoten des Baums (Diagramm) entlang der Breite des Baums (Diagramm). Werden alle Knoten besucht, bricht der Algorithmus ab. BFS ist auch eine Blindsuche. Warteschlangendatenstrukturen werden im Allgemeinen verwendet, um die Implementierung des BFS-Algorithmus zu unterstützen. Algorithmusschritte: 1. Stellen Sie zuerst den Wurzelknoten in die Warteschlange. 2. Entfernen Sie den ersten Knoten aus der Warteschlange und prüfen Sie, ob es sich um das Ziel handelt. Wenn das Ziel gefunden wird, beenden Sie die Suche und geben Sie die Ergebnisse zurück. Andernfalls fügen Sie alle ungetesteten direkten untergeordneten Knoten zur Warteschlange hinzu. 3. Wenn die Warteschlange leer ist, bedeutet dies, dass das gesamte Bild überprüft wurde – das heißt, es gibt kein Ziel, nach dem im Bild gesucht werden muss. Beenden Sie die Suche und geben Sie „Ziel nicht gefunden“ zurück. 4. Wiederholen Sie Schritt 2. Algorithmus 8: Dijkstra-Algorithmus Dijkstra-Algorithmus wurde vom niederländischen Informatiker Etzh entwickelt und von L. Dykstra vorgeschlagen. Der Dijkstra-Algorithmus verwendet die Breitensuche, um das Problem des kürzesten Pfads aus einer Quelle nicht negativ gewichteter gerichteter Graphen zu lösen. Der Algorithmus erhält schließlich einen Baum des kürzesten Pfads. Dieser Algorithmus wird häufig in Routing-Algorithmen oder als Submodul anderer Graphalgorithmen verwendet. Die Eingabe dieses Algorithmus enthält einen gewichteten gerichteten Graphen G und einen Quellscheitelpunkt S in G. Wir verwenden V, um die Menge aller Eckpunkte in G darzustellen. Jede Kante in einem Diagramm ist ein geordnetes Elementpaar, das aus zwei Eckpunkten besteht. (u, v) bedeutet, dass es einen Pfad gibt, der vom Scheitelpunkt u nach v führt. Wir verwenden E, um die Menge aller Kanten in G darzustellen, und das Gewicht der Kante wird durch die Gewichtsfunktion w definiert: E → [0, ∞]. Daher ist w(u, v) das nicht negative Gewicht vom Scheitelpunkt u bis zum Scheitelpunkt v. Das Gewicht einer Kante kann man sich als den Abstand zwischen zwei Eckpunkten vorstellen. Das Gewicht eines Pfades zwischen zwei beliebigen Punkten ist die Summe der Gewichte aller Kanten auf dem Pfad. Es ist bekannt, dass es in V Scheitelpunkte s und t gibt. Der Dijkstra-Algorithmus kann den Pfad mit dem niedrigsten Gewicht (z. B. den kürzesten Pfad) von s nach t finden. Dieser Algorithmus kann auch den kürzesten Weg von einem Scheitelpunkt s zu jedem anderen Scheitelpunkt in einem Diagramm finden. Für gerichtete Graphen ohne negative Gewichte ist der Dijkstra-Algorithmus derzeit der schnellste bekannte Single-Source-Shortest-Path-Algorithmus. Algorithmusschritte: 1. Anfangsbefehl S={V0},T={verbleibende Scheitelpunkte}, der Abstandswert, der dem Scheitelpunkt in T entsprichtfalls vorhanden , d(V0,Vi) ist das Gewicht auf dem -BogenWenn es kein gibt, ist d(V0,Vi) ∞ 2. Wählen Sie einen Scheitelpunkt W aus, dessen Abstandswert von T am kleinsten ist und der nicht in S liegt, und fügen Sie S hinzu.3 Ändern Sie die Abstandswerte der verbleibenden Scheitelpunkte in T: Wenn W als Zwischenscheitelpunkt hinzugefügt wird, verkürzt sich der Abstandswert von V0 zu Vi, dann ändern Sie diesen AbstandswertWiederholen Sie die Schritte 2 und 3 oben, bis S alle Scheitelpunkte enthält, d. h. W=ViAlgorithmus 9: Dynamischer ProgrammieralgorithmusDynamische Programmierung ist eine Methode, die in Mathematik, Informatik und Wirtschaftswissenschaften verwendet wird, um komplexe Probleme zu lösen, indem das ursprüngliche Problem in relativ einfache Teilprobleme zerlegt wird. Dynamische Programmierung eignet sich oft für Probleme mit überlappenden Teilproblemen und optimalen Unterstruktureigenschaften. Dynamische Programmiermethoden benötigen oft viel weniger Zeit als naive Lösungen. Die Grundidee der dynamischen Programmierung ist sehr einfach. Um ein bestimmtes Problem zu lösen, müssen wir grob gesagt seine verschiedenen Teile (d. h. Teilprobleme) lösen und dann die Lösungen für die Teilprobleme kombinieren, um zu einer Lösung für das ursprüngliche Problem zu gelangen. Oft sind viele Teilprobleme sehr ähnlich, daher versucht die dynamische Programmierung, jedes Teilproblem nur einmal zu lösen, wodurch der Rechenaufwand reduziert wird: Sobald die Lösung für ein bestimmtes Teilproblem berechnet wurde, wird sie gespeichert und für den Fall gespeichert, dass dasselbe Teilproblem das nächste Mal benötigt wird Schauen Sie bei der Lösung des Problems direkt in der Tabelle nach. Dieser Ansatz ist besonders nützlich, wenn die Anzahl der wiederholten Teilprobleme exponentiell mit der Größe der Eingabe wächst. Das klassischste Problem der dynamischen Programmierung ist zweifellos das Rucksackproblem. Algorithmusschritte: 1. Optimale Unterkonstruktionseigenschaften. Wenn die optimale Lösung eines Problems Lösungen für Teilprobleme enthält, die ebenfalls optimal sind, sagen wir, dass das Problem optimale Unterstruktureigenschaften hat (d. h. es erfüllt das Optimierungsprinzip). Die optimalen Unterstruktureigenschaften liefern wichtige Anhaltspunkte für dynamische Programmieralgorithmen zur Lösung von Problemen. 2. Überlappung der Teilprobleme. Die überlappende Natur von Teilproblemen bedeutet, dass bei Verwendung eines rekursiven Algorithmus zur Lösung eines Problems von oben nach unten die jedes Mal generierten Teilprobleme nicht immer neue Probleme sind und einige Teilprobleme mehrmals wiederholt berechnet werden. Der dynamische Programmieralgorithmus nutzt die Überlappung dieses Teilproblems. Er berechnet jedes Teilproblem nur einmal und speichert seine Berechnungsergebnisse nur dann in einer Tabelle, wenn es erforderlich ist, das berechnete Teilproblem erneut zu berechnen Sie müssen es in der Tabelle berechnen. Überprüfen Sie einfach die Ergebnisse und steigern Sie die Effizienz. Algorithmus 10: Naive Bayes-Klassifizierungsalgorithmus Der Naive Bayes-Klassifizierungsalgorithmus ist ein einfacher Wahrscheinlichkeitsklassifizierungsalgorithmus, der auf dem Bayes-Theorem basiert. Die Grundlage der Bayes'schen Klassifikation ist das probabilistische Denken. Dabei geht es darum, Argumentations- und Entscheidungsaufgaben zu erledigen, wenn die Existenz verschiedener Bedingungen ungewiss ist und nur die Wahrscheinlichkeit ihres Auftretens bekannt ist. Das probabilistische Denken ist das Gegenstück zum deterministischen Denken. Der Naive-Bayes-Klassifikator basiert auf der Unabhängigkeitsannahme, das heißt, es wird davon ausgegangen, dass jedes Merkmal der Stichprobe nicht mit anderen Merkmalen zusammenhängt. Der Naive Bayes-Klassifikator basiert auf einem genauen natürlichen Wahrscheinlichkeitsmodell und kann im Stichprobensatz des überwachten Lernens sehr gute Klassifizierungsergebnisse erzielen. In vielen praktischen Anwendungen verwendet die Naive-Bayes-Modellparameterschätzung Methoden der Maximum-Likelihood-Schätzung. Mit anderen Worten: Naive-Bayes-Modelle können ohne Verwendung der Bayes'schen Wahrscheinlichkeit oder eines Bayes'schen Modells funktionieren. Vielen Dank, dass Sie dem Blog der Website folgen!

Das Obige hat die zehn besten Programmieralgorithmen vorgestellt, die Programmierern dabei helfen sollen, Meister zu werden, einschließlich inhaltlicher Aspekte. Ich hoffe, dass sie für Freunde, die sich für PHP-Tutorials interessieren, hilfreich sein werden.