Zehn grundlegende praktische Algorithmen, die Programmierer kennen müssen, und ihre Erklärungen

• ### Algorithmus 1: Schnelle Sortierung

Schnelle Sortierung ist ein Sortierungsalgorithmus, der von Tony Hall entwickelt wurde. Im Durchschnitt benötigt man n nlogn Vergleiche für die Sortierung von Projekten. Im schlimmsten Fall benötigt man n nlogn Vergleiche, was jedoch nicht üblich ist. In der Tat ist schnelle Sortierung in der Regel deutlich schneller als andere nlogn-Algorithmen, da die Innenlaufbahn (innerloop) auf den meisten Architekturen sehr effizient umgesetzt werden kann.

Schnelle Sortierung Die Divide-and-Conquer-Strategie wird verwendet, um eine Reihe von Listen in zwei Unterlisten zu unterteilen.

Schritt für Schritt:

• 1. Wählen Sie ein Element aus der Reihe, das als Basiswert (Pivot) bezeichnet wird.
• 1. Reordnen Sie die Reihe, indem alle Elemente, die kleiner als der Referenzwert sind, vor die Referenz gelegt werden, und alle Elemente, die größer als der Referenzwert sind, werden hinter der Referenz gelegt. Die gleiche Anzahl kann auf jeder Seite sein.
• 1. Recursiv (recursive) ordnet die Submenge der Elemente, die kleiner als die Benchmark-Elemente sind, und die Submenge der Elemente, die größer als die Benchmark-Elemente sind.

  Der grundlegende Fall der Regression ist, dass die Größe der Reihe 0 oder 1 ist, d. h. dass sie für immer sortiert ist. Obwohl sie immer wieder zurückfällt, wird der Algorithmus immer wieder aussteigen, da er bei jeder Iteration mindestens ein Element an seine letzte Position bringt.

• ### Algorithmus 2: Stapel-Sortierung

Heapsort ist ein Sortierungsalgorithmus, der mit der Heapsort-Datenstruktur entworfen wurde. Die Heapsort-Struktur ist eine annähernd vollständige Quadratbaumstruktur, die gleichzeitig die Eigenschaft der Heapsort-Struktur erfüllt, dass der Schlüsselwert oder der Index eines Unterknotens immer kleiner als (oder größer als) sein Vaterknot ist.

Die durchschnittliche Zeitkomplexität der Stapel-Sortierung ist O ((nlogn) 。

Schritt für Schritt:

• 1. Erstellen eines H-Hacks[0..n-1]
• 1. Wechseln Sie Stack-Head (maximum) und Stack-End.
• 1. Verkleine den Stapel um 1 und ruf shift_down(0) an, um die Daten an der Spitze des neuen Arrays an die entsprechende Position zu bringen
• 1. Wiederholen Sie Schritt 2, bis der Stapel 1 ist

• Algorithmus 3: Rückführung und Reihenfolge

Mergesort ist ein effizienter Sortier-Algorithmus, der auf Mergesorten basiert. Dieser Algorithmus ist eine sehr typische Anwendung des Divide-and-Conquer-Verfahrens.

Schritt für Schritt:

• 1. Anforderungsspeicher mit der Größe der Summe zweier bereits sortierter Sequenzen, der Speicher für die kombinierte Sequenz
• 1. Setzen Sie zwei Pointers, die jeweils die Anfangspositionen zweier bereits sortierter Sequenzen sind
• 1. Vergleichen Sie die Elemente, auf die zwei Zeiger zeigen, wählen Sie die relativ kleinen Elemente, die in den Verschmelzungsraum eingesetzt werden, und bewegen Sie den Zeiger in die nächste Position
• 1. Wiederholen Sie Schritt 3 bis ein Zeiger am Ende der Reihe ist
• 1. Alle übrigen Elemente einer anderen Sequenz direkt in die Endsequenz der Verschmelzung kopieren

• Algorithmus 4: Zweiteilung

Die Differential-Suche ist eine Suche nach einem bestimmten Element in einer ordnungsgemäßen Array. Die Suche beginnt mit dem mittleren Element der Array und endet, wenn das mittlere Element das gewünschte Element ist. Wenn ein bestimmtes Element größer oder kleiner als das mittlere Element ist, wird in der Hälfte der Array gesucht, die größer oder kleiner als das mittlere Element ist, und der Vergleich beginnt mit dem mittleren Element wie zu Beginn.

• ### Algorithmus 5: BFPRT (linearer Such-Algorithmus)

Die BFPRT-Algorithmen lösen die klassische Aufgabe, aus einer Reihe von n Elementen das k-größere (und k-kleinste) Element zu wählen, und durch geschickte Analyse garantiert BFPRT eine lineare Zeitkomplexität im schlimmsten Fall. Die Idee des Algorithmus ähnelt der Idee der schnellen Reihenfolge, und natürlich wurde die Zeitkomplexität der fünf Algorithmus-Autoren geschickt verarbeitet, damit der Algorithmus im schlimmsten Fall immer noch eine Zeitkomplexität von o (und n) erreicht.

Schritt für Schritt:

• 1. N Elemente in fünf Gruppen aufteilen, in n/5 (obere Grenze) Gruppen.
• 1. Die Mittelwerte für jede Gruppe herausnehmen und eine beliebige Sortiermethode wie z. B. die Einfüge-Sortierung anwenden.
• 1. Die recursive Aufruf-Selection-Algorithmus sucht die Mittelwerte aller Mittelwerte aus dem vorherigen Schritt und setzt sie auf x, wobei bei einer Paarenzahl von Mittelwerten die mittlere als die kleinste ausgesucht wird.
• 1. Spalten Sie die Array mit x, indem Sie die Zahlen kleiner als und gleich x mit k und größer als x mit n-k angeben.
• 1. Wenn i == k, gibt es x; wenn i < k, wird das Element i kleiner als x wiederholt; wenn i> k, wird das Element i-k kleiner als x wiederholt.

  Endbedingung: Wenn n = 1, wird das Element i zurückgegeben.

• Algorithmus 6: DFS (Depth Prioritized Search)

Eine tiefen-erst-such-algorithmus ist ein such-algorithmus, der die tiefe des baumes entlang der knoten des baumes durchquert und die branchen des baumes so tief wie möglich sucht. Wenn alle seiten des nodes v bereits durchforstet sind, wird die suche zurück zu dem beginnenden node auf der seite des gefundenen nodes v durchgeführt.

Die Deep Priority-Suche ist ein klassischer Algorithmus in der Graphik. Mit der Deep Priority-Suche kann eine entsprechende Topologie der Zielgraphik erzeugt werden. Mit der Topologie können viele damit verbundene graphische Probleme wie das Problem des maximalen Pfades bequem gelöst werden.

Die Algorithmus-Schritte werden in der Tiefe vorrangig durchlaufen:

• 1. Besuch der Spitze v;
• 1. Die Grafik wird in der Folge von unbesuchten Anschlüssen in der Nähe von v in die Tiefe vorangestellt, bis alle Gipfel in der Grafik, die mit v verbunden sind, aufgerufen werden.
• 1. Wenn noch nicht zugegriffen worden ist, beginnt man mit einem nicht zugegriffenen Gipfel und beginnt mit einer erneuten Tiefenspitzenführung, bis alle Gipfel des Diagramms besucht sind.

  Die oben beschriebene Beschreibung könnte abstrakt sein, zum Beispiel:

  DFS beginnt mit einem Gipfel v in der Zugriffsgrafik, beginnt mit v und besucht jedes seiner benachbarten Gipfel w1; beginnt dann mit w1 und besucht die Gipfel w2, die mit w1 benachbart sind, aber noch nicht besucht wurden; beginnt dann mit w2 und macht eine ähnliche Zugriffsaktion … und so weiter, bis alle benachbarten Gipfel besucht wurden.

  Gehen Sie dann einen Schritt zurück und gehen Sie zu dem Gipfel zurück, den Sie zuvor besucht haben, um zu sehen, ob weitere benachbarte Gipfel nicht besucht wurden. Wenn ja, besuchen Sie diesen Gipfel und gehen Sie von diesem Gipfel aus aus, um einen ähnlichen Besuch wie zuvor durchzuführen. Wenn nicht, gehen Sie einen weiteren Schritt zurück und suchen.

• Algorithmus sieben: BFS (Breitungsvorrangige Suche)

Breitengröße-Erstsuche (BFS) ist ein Graphik-Such-Algorithmus. Einfach ausgedrückt ist BFS ein Knoten, der von der Wurzel beginnt und die Breite des Baumes durchquert. Wenn alle Knoten aufgerufen werden, wird der Algorithmus abgebrochen.

Schritt für Schritt:

• 1. Zuerst setzen Sie die Wurzeln in die Queue.
• 1. Nehmen Sie den ersten Knoten aus der Reihe und prüfen Sie, ob er das Ziel ist.

  Wenn das Ziel gefunden wird, beendet die Suche und meldet die Ergebnisse. Ansonsten werden alle noch nicht geprüften direkten Unterknoten in die Queue aufgenommen.

• 1. Wenn die Warteschlange leer ist, wurde die gesamte Karte durchsucht, d.h. es gibt keine Suche nach dem Ziel in der Karte. Beende die Suche und schicke die Rückmeldung, die das Ziel nicht findet.
• 1. Wiederholen Sie Schritt 2.

• Algorithmus acht: Die Dijkstra-Algorithmus

Der Dijkstra-Salgorithmus wurde von dem niederländischen Computerwissenschaftler Eizhel Dijkstra entwickelt. Der Dijkstra-Algorithmus verwendet Breitenpriorität-Suche, um die Ein-Quell-Schnellste-Pfad-Problematik für nicht-negative, berechtigte Diagramme zu lösen. Der Algorithmus erhält schließlich einen Schnellsten-Pfad-Baum.

Die Eingabe des Algorithmus beinhaltet ein gewichtetes Richtdiagramm G und einen Quellpunkt S in G. Die Seiten jedes Diagramms sind ordentliche Elementpaare, die von den beiden Gipfeln gebildet werden. Die Seiten werden durch die Gewichtungsfunktion w:E→[0,∞] definiert.

Daher ist w (u,v) das nicht-negative Gewicht von u bis v. Das Gewicht einer Seite kann als die Entfernung zwischen zwei Gipfeln verstanden werden. Das Gewicht eines Weges zwischen zwei Punkten ist die Summe der Gewichte aller Seiten auf dem Weg. Es gibt bekanntlich Gipfel in V, die s und t enthalten.

Schritt für Schritt:

• 1. Anfangswert S={V0}, T={restliche Gipfel}, Distanz der Gipfel in T Wenn ,d(V0,Vi) als Gewicht auf dem -Bogen vorhanden ist Wenn nicht vorhanden ist, ist d (V0,Vi) gleich
• 1. Wählen Sie aus T einen Gipfel W, dessen Abstand der kleinste ist und der nicht in S ist, und schließen Sie ihn S an
• 1. Änderung des Abstands von den Gipfeln in den übrigen T: Wenn W als mittlerer Gipfel hinzugefügt wird, wird der Abstand von V0 bis Vi verkürzt. Dieser Abstand wird geändert

  Wiederholen Sie die Schritte 2 und 3, bis alle Gipfel in S enthalten sind, also bis W = Vi

• Algorithmus 9: Dynamische Planung

Dynamische Programmierung ist eine Methode, die in Mathematik, Computerwissenschaften und Ökonomie verwendet wird, um komplexe Probleme zu lösen, indem die ursprünglichen Probleme in relativ einfache Subprobleme zerlegt werden. Dynamische Programmierung wird häufig für Probleme mit überlappenden Subproblemen und Problemen mit optimaler Struktur verwendet, wobei die Dynamische Programmierung viel weniger Zeit in Anspruch nimmt als die einfache Lösung.

Die Grundidee hinter der dynamischen Planung ist sehr einfach. Im Allgemeinen ist es notwendig, die verschiedenen Teile einer gegebenen Problematik zu lösen, um die Lösung der unteren Probleme zu erhalten. In der Regel sind viele Unterprobleme sehr ähnlich, weshalb die dynamische Planungsmethode versucht, die einzelnen Unterprobleme nur einmal zu lösen, um die Rechenleistung zu reduzieren: Sobald die Lösung einer gegebenen Unterproblematik berechnet wurde, wird sie in Erinnerung gespeichert, um sie beim nächsten Mal, wenn die gleiche Unterproblematik zu lösen ist, direkt zu erfassen.

Die klassischsten Fragen zur dynamischen Planung sind die der Rucksäcke.

Schritt für Schritt:

1. Die optimale Struktur-Eigenschaft. Wenn die optimale Lösung des Problems auch eine optimale Lösung für die untergeordneten Probleme enthält, bezeichnen wir das Problem als eine optimale Struktur-Eigenschaft (das heißt, es erfüllt den Grundsatz der Optimierung). Die optimale Struktur-Eigenschaft liefert wichtige Hinweise für die Lösung des Problems mit einem dynamischen Planungsalgorithmus.

2. Überschneidung von Unterproblemen. Unterproblemüberschneidung bedeutet, dass bei der Lösung von Problemen von oben nach unten mit einem Recursionsalgorithmus nicht immer ein neues Problem erzeugt wird. Einige Unterprobleme werden mehrmals berechnet. Dynamische Planungsalgorithmen nutzen diese Überschneidung von Unterproblemen, berechnen für jede Unterfrage nur einmal und speichern ihre Berechnungsergebnisse in einer Tabelle.

• ### Algorithmus 10: Einfachheit bei der Bayes-Klassifizierung

Ein einfacher Bayesianer Klassifikator ist ein einfacher Wahrscheinlichkeitsklassifikator, der auf den Bayesianischen Theorien basiert. Bei der Bayesianischen Klassifizierung handelt es sich um Wahrscheinlichkeitsreduktion, also darum, wie man in der Lage ist, zu denken und Entscheidungen zu treffen, wenn die Existenz verschiedener Bedingungen unsicher ist und nur die Wahrscheinlichkeit dafür bekannt ist. Wahrscheinlichkeitsreduktion entspricht der Bestimmtheit.

Ein einfacher Bayes-Klassifikator beruht auf einem präzisen Modell der natürlichen Wahrscheinlichkeit und kann in einer Gruppe von Proben mit überwachtem Lernen sehr gute Klassifizierungseffekte erzielen. In vielen praktischen Anwendungen werden die Parameter des einfachen Bayes-Modells mit der Methode der höchsten Wahrscheinlichkeitsschätzung geschätzt, was bedeutet, dass ein einfaches Bayes-Modell ohne Bayes-Wahrscheinlichkeit oder irgendein Bayes-Modell funktioniert.

Trotz dieser simplen Gedanken und allzu vereinfachten Annahmen kann ein simpler Bayesianer in vielen komplexen Realitätssituationen ziemlich gut funktionieren.