Schnelle Sortierung ist eine Sortierung, die von Tony Hall entwickelt wurde. Im Durchschnittsfall erfordert die Sortierung von n Objekten O (nlogn) Vergleiche. Im Schlimmstenfall erfordert sie O (n2) Vergleiche, was jedoch nicht üblich ist. In der Tat ist schnelle Sortierung oft deutlich schneller als andere O (nlogn) Algorithmen, da ihre innere Schleife (inner loop) in den meisten Architekturen sehr effizient umgesetzt werden können.
Schnelle Sortierung verwendet die Strategie "Divideandconquer", um eine Liste in zwei Unterlisten zu unterteilen.
Algorithmus-Schritte:
1. Wählen Sie ein Element aus der Zahlenreihe, das als Pivot bezeichnet wird.
2, Reorderieren der Zahlenreihe, alle Elemente kleiner als der Referenzwert vor dem Referenzwert und alle Elemente größer als der Referenzwert hinter dem Referenzwert; nach dem Verlassen dieser Partition befindet sich der Referenzwert in der Mitte der Zahlenreihe. Dies wird als Partition-Operation bezeichnet.
3. Recursive Reihenfolge der Unterarten von Elementen, die kleiner als ein Referenzwert sind, und der Unterarten von Elementen, die größer als ein Referenzwert sind.
Das Grundspiel der Regression ist, dass die Arraygröße null oder eins ist, d.h. dass sie immer gut sortiert ist. Obwohl sie immer wieder zurückfällt, tritt die Algorithmus immer aus, weil sie bei jeder Iteration mindestens ein Element in seine letzte Position bringt.
Heapsort ist ein Sortierungs-Algorithmus, der mit einem solchen Datensatz ausgestattet ist. Ein Stapel ist eine Struktur, die sich annähernd vollständig auf einen Binärbaum bezieht und gleichzeitig die Eigenschaften des Stapels erfüllt: der Schlüsselwert oder Index eines Unterknotens ist immer kleiner als (oder größer als) sein Elternknoten.
Die durchschnittliche Zeitkomplexität der Stapelsortierung ist O (nlogn).
Algorithmus-Schritte:
1. Erstellen Sie einen Stapel H [0...n-1]
2. Wechseln Sie den Stapelvorgang (maximal) und den Stapelrücken.
3. Vergrößern Sie den Stapel um 1 und rufen Sie Shift_down ((0), um die Daten an der Spitze der neuen Array in die richtige Position zu bringen
4. Wiederholen Sie Schritt 2 bis die Stapelgröße 1 ist
Mergesort ist ein effektiver Sorting-Algorithmus, der auf dem Einsatz von Mergesort basiert. Der Algorithmus ist eine sehr typische Anwendung des DivideandConquer-Verfahrens.
Algorithmus-Schritte:
1, einen Antragsraum, der so groß ist, dass er die Summe von zwei bereits sortierten Sequenzen ist, die für die Speicherung der zusammengeführten Sequenzen verwendet werden.
2. Setzen Sie zwei Zeiger, die jeweils an der Anfangsposition zweier sortierter Sequenzen stehen.
3. Vergleichen Sie die Elemente, auf die die beiden Zeiger verweisen, wählen Sie ein relativ kleines Element in den Verschmelzungsraum und bewegen Sie den Zeiger zur nächsten Position
4. Wiederholen Sie Schritt 3 bis ein Zeiger am Ende der Reihe ist.
5. Kopiert alle übrigen Elemente der anderen Sequenz direkt zum Ende der kombinierten Sequenz
Ein zweistufiges Suchalgorithmus ist ein Suchalgorithmus, der nach einem bestimmten Element in einer geordneten Array sucht. Der Suchprozess beginnt mit dem mittleren Element der Array und endet, wenn das mittlere Element genau das ist, was gesucht werden soll. 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 wie zu Beginn wird von dem mittleren Element angefangen.
Die BFPRT-Algorithmen lösen die klassische Aufgabe, aus einer Reihe von n Elementen das k-größte (k-kleine) Element zu wählen. Durch geschickte Analysen kann BFPRT garantieren, dass es bei schlimmstem Fall immer noch eine lineare Zeitkomplexität hat.
Algorithmus-Schritte:
1, die n Elemente in einer Gruppe von jeweils 5 Gruppen unterteilt in n/5 (obere Grenze) Gruppen.
2. Entfernen Sie die Mittelwerte der einzelnen Gruppen mit beliebigen Sortungsmethoden, wie z.B. Einfügen von Sorturen.
3. Der recursive Aufruf-Selektionsalgorithmus sucht nach dem Mittelwert aller Mitteln in dem vorherigen Schritt, der als x gesetzt ist, und bei einer paar Mitteln als kleiner als der mittlere eingestellt.
4. Die Array wird mit x geteilt, wobei die Zahl kleiner als x gleich k ist und die Zahl größer als x n - k ist.
5, wenn i==k, zurückkehrt x; wenn i
Endbedingung: Bei n = 1 wird das kleine Element i zurückgegeben.
Die Deep-First-Search-Algorithmen sind eine Art Suchalgorithmen. Sie durchqueren die Nodes des Baumes in der Tiefe des Baumes und verzweigen sie so tief wie möglich. Wenn alle Seiten des Baumes v durchsucht wurden, wird die Suche auf den Anfangspunkt an der Seite des gefundenen Baumes zurückgeleitet.
Die Verwendung von Deep-Priority-Search-Algorithmen erzeugt eine entsprechende Topologiesortierung des Zieldiagramms. Die Verwendung von Topologiesortierungen kann viele verwandte Graphikprobleme, wie z. B. das Problem des größten Weges, bequem lösen.
Die Schritte des Algorithmus werden in der Tiefe priorisiert:
1. Zugriff auf die Spitze v;
2. Ab den nicht aufgerufenen angrenzenden Anschlüssen von v wird die Grafik abwechselnd mit Tiefenvorrang durchlaufen; bis alle Spitzen der Grafik, die mit dem Pfad von v übereinstimmen, aufgerufen werden;
3. Wenn es noch unbesuchte Spitzen in der Zeichnung gibt, geht man von einem unbesuchten Spitzenpunkt aus und führt die Tiefenvorzugskontrolle erneut durch, bis alle Spitzen in der Zeichnung besucht sind.
Die Beschreibung oben kann eher abstrakt sein, zum Beispiel:
DFS geht von v aus, beginnt mit einem der Gipfel v in der Zugriffskala und geht zu jedem seiner benachbarten Gipfel w1; geht von w1 aus, geht zu den Gipfeln w2, die an w1 angrenzen, aber noch nicht besucht wurden; geht dann von w2 aus, macht einen ähnlichen Besuch,... und so weiter, bis man zu den Gipfeln u gelangt, die von allen benachbarten Gipfeln besucht wurden.
Gehen Sie dann einen Schritt zurück, um zu dem Gipfel zurückzukehren, den Sie zuvor gerade besucht haben, um zu sehen, ob es noch andere nicht besuchte Nachbarspitzen gibt. Wenn ja, besuchen Sie diesen Gipfel, und starten Sie dann von diesem Gipfel aus, um einen ähnlichen Besuch zu machen. Wenn nicht, gehen Sie einen Schritt zurück und suchen Sie. Wiederholen Sie den Vorgang, bis alle Gipfel in der Verbindungskarte besucht wurden.
Breite-First-Search ist ein Grafik-Search-Algorithmus. Einfach ausgedrückt, ist BFS der Beginn eines Wurzelnodes, der die Breite des Baumes entlang des Baumdiagramms durchläuft. Wenn alle Nodes besucht werden, wird der Algorithmus abgebrochen.
Algorithmus-Schritte:
1. Zuerst setzen wir den Stammknoten in die Schlange.
2. Nehmen Sie den ersten Knoten aus der Reihe und prüfen Sie, ob er ein Ziel ist.
Wenn das Ziel gefunden wird, wird die Suche beendet und die Ergebnisse zurückgesendet. Ansonsten werden alle noch nicht geprüften direkten Sub-Nodes in die Warteschlange aufgenommen.
3. Wenn die Warteschlange leer ist, bedeutet dies, dass die gesamte Grafik überprüft wurde und dass keine Suchanfragen in der Grafik gefunden wurden.
4. Wiederholen Sie Schritt 2.
Der Dijkstra-Salgorithmus wurde von dem niederländischen Computerwissenschaftler Eichel Dijkstra entwickelt. Der Dijkstra-Algorithmus nutzt eine Breitgewichtungssuche, um den kürzesten Weg eines nicht-negativ autorisierten Wegdiagramms zu lösen.
Die Eingabe der Algorithmus umfasst eine gewichtete Richtungsdiagramm G und einen Quellpunkt S in G. Wir bezeichnen V als die Sammlung aller Spitzen in G. Jede Seite in der Diagramm ist ein paar von ordnungsgemäßen Elementen, die von zwei Spitzen gebildet werden. U, v zeigen einen Pfad von den Spitzen u zu v. Wir bezeichnen E als die Sammlung aller Seiten in G, deren Gewicht durch die Gewichtungsfunktion w:E→[0,∞] definiert wird.
Daher ist w (u, v) das nichtnegative Gewicht von u zu v. Das Gewicht der Seite kann als die Entfernung zwischen den beiden Spitzen vorgestellt werden. Das Gewicht des Weges zwischen den beiden Punkten ist die Summe der Gewichte aller Seiten auf dem Weg. Es gibt bekannte Spitzen s und t in V. Die Dijkstra-Algorithmus kann den geringsten Gewichtsweg von s zu t finden.
Algorithmus-Schritte:
1, bei S = {V0}, T = {resten Spitzen}, T ist der Abstand zwischen den Spitzen
Wenn
2. Wählen Sie aus T einen Gipfel W, dessen Abstand der geringste ist und der nicht in S ist, und fügen Sie S hinzu
3, Änderung des Abstandswerts zu den restlichen T-Spitzen: Wenn man W als mittlere Spitze hinzufügt und den Abstandswert von V0 bis Vi verkürzt, ändert man diesen Abstandswert
Wiederholen Sie die Schritte 2,3 bis alle Spitzen in S enthalten sind, also W = Vi.
Dynamische Programmierung ist eine Methode, die in Mathematik, Computerwissenschaften und Wirtschaftswissenschaften verwendet wird, um komplexe Probleme zu lösen, indem die ursprünglichen Probleme in relativ einfache Teilprobleme aufgeteilt werden.
Die Grundidee hinter Dynamic Planning ist sehr einfach. Im Allgemeinen müssen wir, um ein Problem zu lösen, verschiedene Teile des Problems lösen ("Studentenprobleme") und die Lösung der Subproblematik wieder zusammenfügen, um die Lösung des Problems zu finden. Oft sind viele Subprobleme so ähnlich, dass Dynamic Planning versucht, jedes Subproblem nur einmal zu lösen, wodurch die Rechenmenge reduziert wird: Sobald eine Lösung für ein gegebenes Subproblem berechnet wurde, wird es im Gedächtnis gespeichert, um es direkt zu überprüfen, wenn das nächste Mal ein solches Problem gelöst werden muss. Diese Praxis ist besonders nützlich, wenn die Anzahl der wiederkehrenden Subprobleme exponentiell an der Größe der Eingabe wächst.
Die klassische Frage der dynamischen Planung ist die Frage des Rucksacks.
Algorithmus-Schritte:
1. Optimumsstruktur. Wenn die Lösung eines Problems, das in der Optimumslösung enthalten ist, auch optimal ist, dann ist das Problem optimal (d. h. es erfüllt die Optimumsprinzipien). Die Optimumsstruktur liefert wichtige Hinweise für die Lösung von Problemen mit Dynamikplanungsalgorithmen.
2. Überschneidung der Teilprobleme. Überschneidung der Teilprobleme bedeutet, dass bei einer Top-Down-Lösung mit einem recursive Algorithmus nicht immer ein neues Problem entsteht, sondern dass einige Teilprobleme mehrmals berechnet werden. Die dynamische Planungsalgorithmen nutzen die Überschneidung der Teilprobleme, indem sie jedes Teilproblem nur einmal berechnen und dann in einer Tabelle speichern, und wenn es wieder einmal notwendig ist, bereits berechnete Teilprobleme zu berechnen, sehen Sie einfach das Ergebnis in der Tabelle, um höhere Effizienz zu erzielen.
Ein einfaches Bayes-Klassifizierungs-Algorithmus ist ein einfaches Wahrscheinlichkeits-Klassifizierungs-Algorithmus, das auf Bayes-Theorem basiert. Das Basis-Algorithmus für Bayes-Klassifizierung ist die Wahrscheinlichkeits-Argumentation, also wie man Argumentationen und Entscheidungsaufgaben macht, wenn verschiedene Bedingungen unsicher sind und nur die Wahrscheinlichkeit ihrer Entstehung bekannt ist.
Ein einfaches Bayes-Klassifizierungsgerät setzt auf ein präzises natürliches Wahrscheinlichkeitsmodell und erzielt sehr gute Klassifizierungseffekte in Stichprobengruppen mit überwachtem Lernen. In vielen praktischen Anwendungen werden die Parameter des einfachen Bayes-Modells mit maximaler Wahrscheinlichkeit geschätzt, d. h. das einfache Bayes-Modell funktioniert ohne Bayes-Wahrscheinlichkeit oder jedes Bayes-Modell.
Trotz dieser einfachen Ideen und übermäßig vereinfachten Annahmen kann ein einfacher Bayes-Klassifikator in vielen komplexen Realitäten ziemlich gut funktionieren.