Wie kann der Aufbau eines Heaps eine Zeitkomplexität von O(n) haben?

Question

Kann mir jemand erklären, wie man einen Haufen bauen kann O(n) Komplexität?

Das Einfügen eines Elements in einen Heap ist O(log n) und die Einfügung wird n/2 Mal wiederholt (der Rest sind Blätter, die die Heap-Eigenschaft nicht verletzen können). Dies bedeutet also, dass die Komplexität wie folgt sein sollte O(n log n) würde ich denken.

Mit anderen Worten, für jedes Element, das wir "heapify", hat es das Potenzial, zu filtern (dh, zu sichten) einmal für jede Ebene für den Haufen so weit (das ist log n Ebenen).

Was übersehe ich?

Answer 1

Bei der Bildung des Haufens beginnen wir mit der Höhe, logn -1 (wobei logn die Höhe des Baumes mit n Elementen ist). Für jedes Element, das sich auf der Höhe 'h' befindet, gehen wir maximal bis zu (logn -h) Höhe nach unten.

    So total number of traversal would be:-
    T(n) = sigma((2^(logn-h))*h) where h varies from 1 to logn
    T(n) = n((1/2)+(2/4)+(3/8)+.....+(logn/(2^logn)))
    T(n) = n*(sigma(x/(2^x))) where x varies from 1 to logn
     and according to the [sources][1]
    function in the bracket approaches to 2 at infinity.
    Hence T(n) ~ O(n)

Answer 2

@bcorso hat bereits den Beweis für die Komplexitätsanalyse erbracht. Aber für diejenigen, die die Komplexitätsanalyse noch lernen, möchte ich Folgendes hinzufügen:

Ihr ursprünglicher Fehler beruht auf einer Fehlinterpretation der Bedeutung der Aussage "Einfügen in einen Heap dauert O(log n) Zeit". Das Einfügen in einen Heap ist in der Tat O(log n), aber Sie müssen wissen, dass n die Größe des Heaps ist während der Insertion .

Im Zusammenhang mit dem Einfügen von n Objekten in einen Heap ist die Komplexität der i-ten Einfügung O(log n_i), wobei n_i die Größe des Heaps zum Zeitpunkt der Einfügung i ist. Nur die letzte Einfügung hat eine Komplexität von O (log n).

Answer 3

Angenommen, Sie haben N Elemente in einem Heap. Dann wäre seine Höhe Log(N)

Wenn Sie nun ein weiteres Element einfügen wollen, dann wäre die Komplexität : Log(N) müssen wir den ganzen Weg vergleichen UP zur Wurzel.

Jetzt haben Sie N+1 Elemente & Höhe = Log(N+1)

Verwendung von Induktion Technik kann nachgewiesen werden, dass die Komplexität des Einfügens logi .

Jetzt mit

log a + log b = log ab

Dies vereinfacht sich zu : logi=log(n!)

was eigentlich ein O(NlogN)

Aber

Wir machen hier etwas falsch, da wir in allen Fällen nicht an die Spitze gelangen. Daher können wir bei der Ausführung meistens feststellen, dass wir nicht einmal die Hälfte des Baumes hinaufgehen. Daher kann diese Schranke optimiert werden, um eine andere, engere Schranke zu erhalten, indem die in den obigen Antworten angegebene Mathematik verwendet wird.

Diese Erkenntnis kam mir nach einem ausführlichen Durchdenken und Experimentieren auf Heaps.

Answer 4

Im Grunde genommen wird beim Aufbau eines Heaps nur an Nicht-Blatt-Knoten gearbeitet... und die geleistete Arbeit ist die Menge an Swapping nach unten, um die Heap-Bedingung zu erfüllen... mit anderen Worten (im schlimmsten Fall) ist die Menge proportional zur Höhe des Knotens... alles in allem ist die Komplexität des Problems proportional zur Summe der Höhen aller Nicht-Blatt-Knoten... das ist (2^h+1 - 1)-h-1=n-h-1= O(n)

Answer 5

Aufeinanderfolgende Einfügungen können durch beschrieben werden:

T = O(log(1) + log(2) + .. + log(n)) = O(log(n!))

Durch Starling-Approximation, n! =~ O(n^(n + O(1))) daher T =~ O(nlog(n))

Ich hoffe, das hilft, der optimale Weg O(n) ist die Verwendung des Build-Heap-Algorithmus für eine bestimmte Menge (die Reihenfolge spielt keine Rolle).