Wie ist der Bottom-up-Ansatz der Haufenkonstruktion der Ordnung O (n)? Anany Levitin sagt in seinem Buch, dass dies effizienter ist als der Top-Down-Ansatz, der von der Ordnung O (log n) ist. Warum?Warum ist der Top-Down-Ansatz der Heap-Konstruktion weniger effizient als der Bottom-Up-Ansatz, obwohl seine Wachstumsordnung niedriger O (log n) gegenüber O (n) ist?
Das scheint mir wie ein Tippfehler.
Es gibt zwei Standardalgorithmen zum Erstellen eines Heaps. Die erste besteht darin, mit einem leeren Heap zu beginnen und Elemente nacheinander nacheinander einzufügen. Jede einzelne Einfügung benötigt Zeit O (log n), so dass wir die Kosten für diesen Stil der Heapbildung bei O (n log n) nach oben begrenzen können. Es stellt sich heraus, dass die Laufzeit im schlimmsten Fall Θ (n log n) ist, was passiert, wenn Sie die Elemente in umgekehrter Reihenfolge einfügen. Der andere Ansatz ist der Heap-Algorithmus, der den Heap direkt erstellt, indem er mit jedem Element in seinem eigenen binären Heap beginnt und sie progressiv zusammenfügt. Dieser Algorithmus läuft unabhängig von der Eingabe in der Zeit O (n).
Der Grund, warum der erste Algorithmus Zeit benötigt Θ (n log n) ist, dass, wenn Sie die zweite Hälfte der einzufügenden Elemente betrachten, Sie sehen, dass jeder von ihnen in einen Haufen mit der Höhe eingefügt wird Θ (log n), so dass die Kosten für jede Blase höher sein können. Da es n/2 Elemente gibt und jedes von ihnen Zeit braucht, um Θ (log n) einzufügen, ist die Worst-Case-Laufzeit Θ (n log n).
Auf der anderen Seite verbringt der Heap-Algorithmus die meiste Zeit damit, auf kleinen Haufen zu arbeiten. Die Hälfte der Elemente wird in Höhen von 0, ein Viertel in Höhen von 1, ein Achtel in Höhen von 2, usw. eingefügt. Dies bedeutet, dass der Großteil der Arbeit in das Einfügen von Elementen in kleine Haufen, die wesentlich schneller ist, verbracht wird.
Wenn Sie erwägen, tauschen Ihre grundlegenden Betrieb zu sein -
In Top-down-Konstruktion wird der Baum aufgebaut erste und eine heapify Funktion auf dem Knoten.Verfahren schlimmsten Fall aufgerufen wird, würde log n mal tauschen (sichten die Element an die Spitze des Baumes, wo die Höhe des Baumes log n) für alle n/2 Blattknoten ist. Dies führt zu einer oberen Grenze von O (n log n).
In der Bottom-Up-Konstruktion gehen Sie davon aus, dass alle Blattknoten im ersten Durchgang in der richtigen Reihenfolge sind. Heapify wird jetzt nur auf n/2 Knoten aufgerufen. Auf jeder Ebene erhöht sich die Anzahl der möglichen Swaps, aber die Anzahl der Knoten, auf denen sie stattfindet, nimmt ab.
Zum Beispiel - Auf der Ebene direkt über Blattknoten, haben wir n/4 Knoten, die jeweils höchstens 1 Tausch haben können. Auf seiner übergeordneten Ebene haben wir n/8 Knoten, die jeweils höchstens 2 Swaps haben können und so weiter. Bei der Summierung erhalten wir eine O (n) Effizienz für die Bottom-up-Konstruktion eines Heaps.
Ist der Heap-Algorithmus im Vergleich zum Top-Down-Ansatz in Bezug auf Insertionen nicht weniger effizient? Da der Top-Down-Ansatz O (log n) für die Einfügung verwendet, aber für die Heap-Funktion, fügen wir zuerst die Elemente in der Reihenfolge ein und haufen dann, was O (n) ist. Wenn also zu viele Elemente nacheinander eingefügt werden sollen, würde Heap- figure als O (n2) fungieren, was weniger effizient ist als O (n log n) von oben nach unten? –
Sie sind entworfen, um verschiedene Dinge zu tun. Der Heap-Algorithmus ist für den Fall, dass Sie bereits alle Elemente haben, die Sie in den Heap verfügbar machen möchten, und der andere Ansatz funktioniert, wenn Sie nicht im Voraus wissen, wie viele Elemente Sie haben oder was sie sind . Wenn Sie Elemente einzeln nacheinander abrufen, ist der Heap-Algorithmus nicht so gut. – templatetypedef
Das hat geholfen. Danke für die Erklärung. –