Ich habe Sortiermethoden gelesen, die Bubble-Sortierung, Auswahl-Sortierung, Merge-Sortierung, Heap-Sortierung, Bucket-Sortierung usw. enthalten. Sie enthalten auch Zeitkomplexität, die uns hilft zu wissen, welche Sortierung effizient ist. Also hatte ich eine grundlegende Frage. Wenn wir Daten enthalten, werden wir sortieren. Die Zeitkomplexität ist einer der Parameter, die uns helfen, die Sortiermethode zu bestimmen. Aber haben wir einen anderen Parameter, um die Sortiermethode zu wählen?.
Ich versuche nur, die Sortierung für ein besseres Verständnis herauszufinden.
Eine Abfrage über die Sortierung des Heapspeichers:
Wo verwenden wir Heap sort?
Was ist der größte Vorteil der Heap-Sortierung (außer der Zeitkomplexität O (n log n))?
Was ist der Nachteil der Heap-Sortierung?
Was ist Build-Zeit für Heap? (Ich habe O (n) gehört, bin mir aber nicht sicher.)
Jedes Szenario, in dem wir die Heap-Sortierung oder die Heap-Sortierung verwenden müssen, ist die bessere Option (außer der Priority-Queue)?
Bevor wir die Heap-Sortierung für Daten anwenden, welchen Parameter untersuchen wir in Daten?
Die zwei wichtigsten theoretischen Merkmale von Sortieralgorithmen sind die zeitliche Komplexität und die räumliche Komplexität.
Im Allgemeinen lässt Zeitkomplexität uns wissen, wie sich die Leistung des Algorithmus ändert, wenn die Größe des Datensatzes zunimmt . Dinge zu beachten:
Ähnlich beschreibt die Raumkomplexität, wie viel Speicherplatz ein Algorithmus benötigt, um ausgeführt zu werden. Zum Beispiel benötigt eine einfache Sortierung wie Einfügesortierung eine zusätzliche feste Menge an Speicherplatz, um den Wert des aktuell vorhandenen Elements zu speichern eingefügt. Dies ist eine Hilfsraumkomplexität von O (1) - sie ändert sich nicht mit der Größe der Eingabe. merge sort erstellt jedoch während der Ausführung zusätzliche Arrays im Speicher mit einer zusätzlichen Raumkomplexität von O (n). Dies bedeutet, dass die Menge an zusätzlichem Speicherplatz, die benötigt wird, linear mit der Größe der Eingabe korreliert ist.
Natürlich ist das Design von Algorithmen oft eine Abwägung zwischen Zeit und Raum - Algorithmen mit einer geringen Raumkomplexität benötigen möglicherweise mehr Zeit, und Algorithmen mit einer geringen Zeitkomplexität benötigen möglicherweise mehr Platz.
Für weitere Informationen finden Sie dieses Tutorial hilfreich.
Um Ihre aktualisierte Frage zu beantworten, können Sie die Wikipedia-Seite auf Heap Sort nützlich finden.
Wenn Sie Kriterien für die Art der Sortierung angeben, sind hier einige weitere Punkte zu beachten.
Die Menge an Daten, die Sie haben: Sie haben zehn, einhundert, tausend oder Millionen von zu sortierenden Artikeln.
Komplexität des Algorithmus: Je komplexer, desto mehr Tests müssen durchgeführt werden, um sicherzustellen, dass sie korrekt sind. Für kleine Mengen ist eine Bubble-Sortierung oder schnelle Sortierung einfach zu programmieren und zu programmieren, und andere Arten, die für die Menge der Daten, die sortiert werden müssen, übertrieben sein können.
Wie viel Zeit wird zum Sortieren benötigt: Wenn Sie ein großes Set haben, dauert das Bubble / Quick Sort viel Zeit, aber wenn Sie viel Zeit haben, ist das kein Problem. Die Verwendung eines komplexeren Algorithmus verringert jedoch die Sortierzeit, allerdings auf Kosten von mehr Aufwand beim Codieren und Testen, was sich lohnen kann, wenn die Sortierung von lang (Stunden / Tage) zu kürzerer Zeit geht.
Die Daten selbst: Sind die Daten für alles gleich? Für einige Arten können Sie eine lineare Liste erstellen. Wenn Sie also etwas über die Zusammensetzung der Daten wissen, kann es hilfreich sein, zu bestimmen, welcher Algorithmus für den Aufwand ausgewählt werden soll.
Die Menge der verfügbaren Ressourcen: Verfügen Sie über viel Speicher, in dem Sie alle Elemente speichern, oder müssen Sie Elemente auf der Festplatte speichern? Wenn alles nicht in den Speicher passen kann, kann das Zusammenführen besser sein, während das andere besser ist, wenn Sie mit allem im Speicher arbeiten.
Tags und Links c++ data-structures