Wie kann ein Haufen gebaut werden? O(n) zeitliche Komplexität?

Ihre Analyse ist korrekt. Es ist jedoch nicht eng. 

Es ist nicht wirklich einfach zu erklären, warum das Erstellen eines Heapspeichers eine lineare Operation ist. Sie sollten sie besser lesen.

Eine große Analyse des Algorithmus ist hier zu sehen.

Die Hauptidee ist, dass im build_heap-Algorithmus die tatsächlichen heapify-Kosten nicht für alle Elemente O(log n) sind.

Wenn heapify aufgerufen wird, hängt die Laufzeit davon ab, wie weit sich ein Element in der Baumstruktur nach unten bewegt, bevor der Prozess beendet wird. Mit anderen Worten, es hängt von der Höhe des Elements im Heap ab. Im schlimmsten Fall geht das Element möglicherweise bis zur Blattebene hinunter. 

Zählen wir die geleistete Arbeit Stufe für Stufe.

Auf der untersten Ebene gibt es 2^(h)-Knoten, wir rufen jedoch keine heapify auf, also ist die Arbeit 0. Auf der nächsten Ebene gibt es 2^(h − 1)-Knoten, die sich jeweils um 1 Ebene nach unten bewegen können. Auf der dritten Ebene von unten gibt es 2^(h − 2)-Knoten, und jeder kann sich um 2 Ebenen nach unten bewegen.

Da nicht alle Heapify-Operationen O(log n) sind, erhalten Sie O(n).

Intuitiv:

"Die Komplexität sollte O (nLog n) sein ... für jedes Element, das wir" heapifizieren ", besteht die Möglichkeit, dass Sie für jedes Level für den Heap (das heißt log n-Level) einmal herunterfiltern muss.

Nicht ganz. Ihre Logik erzeugt keine engen Grenzen - sie überschätzt die Komplexität jedes Heapizes. Wenn von unten nach oben gebaut, kann das Einfügen (heapify) viel weniger als O(log(n)) sein. Der Prozess ist wie folgt:

(Schritt 1) ​​Die ersten n/2-Elemente werden in der untersten Zeile des Heapspeichers angezeigt. h=0, daher ist keine Heapifizierung erforderlich.

(Schritt 2) Die nächsten n/22-Elemente gehen von unten in die erste Zeile. h=1, heapify filtert 1 Ebene nach unten.

(Schritt i) Die nächsten n/2i-Elemente werden in der Reihe i von unten nach oben verschoben. h=i, heapify filtert i.

(Schritt log (n)) Das letzte n/2log2(n) = 1-Element geht von unten in die Zeile log(n). h=log(n), heapify-Filter log(n) nimmt ab.

HINWEIS: Nach dem ersten Schritt befinden sich 1/2 der Elemente (n/2) bereits im Heap, und wir mussten nicht einmal heapify aufrufen. Beachten Sie auch, dass nur ein einzelnes Element, die Wurzel, tatsächlich die volle Komplexität von log(n) aufweist.

Theoretisch:

Die Gesamtschritte N, um einen Heap der Größe n zu erstellen, können mathematisch geschrieben werden. 

Bei Höhe i haben wir (oben) gezeigt, dass es n/2i+1 Elemente gibt, die heapify aufrufen müssen, und wir wissen, dass heapify bei Höhe iO(i) ist. Das gibt:

Die Lösung der letzten Summation kann gefunden werden, indem die Ableitung beider Seiten der bekannten geometrischen Reihengleichung genommen wird:

Das Einfügen von x = 1/2 in die obige Gleichung ergibt 2. Das Einfügen in die erste Gleichung ergibt:

Somit ist die Gesamtzahl der Schritte von der Größe O(n)

Es wäre O (n log n), wenn Sie den Heap durch wiederholtes Einfügen von Elementen erstellen. Sie können jedoch einen neuen Heap-Speicher effizienter erstellen, indem Sie die Elemente in beliebiger Reihenfolge einfügen und anschließend einen Algorithmus anwenden, um sie in der richtigen Reihenfolge zu "heapifizieren" (abhängig vom Heap-Typ).

Siehe http://en.wikipedia.org/wiki/Binary_heap , "Einen Haufen erstellen" für ein Beispiel. In diesem Fall arbeiten Sie im Wesentlichen von der untersten Ebene der Baumstruktur aus und tauschen übergeordnete und untergeordnete Knoten aus, bis die Heap-Bedingungen erfüllt sind. 

Wie wir wissen, ist die Höhe eines Heaps log (n) , wobei n die Gesamtzahl der Elemente ist. Lets stellen sie als h dar
Wenn wir die Heapifizierungsoperation ausführen, bewegen sich die Elemente auf der letzten Ebene ( h ) nicht einmal um einen Schritt.
Die Anzahl der Elemente auf der vorletzten Ebene ( h-1 ) beträgt 2 ^h-1 und sie können sich bei max 1 level bewegen (während der Heapifizierung). 
Ähnlich für die i ^{th ,} Ebene haben wir 2 ^ich Elemente, die h-i Positionen verschieben können.

Daher Gesamtzahl der Züge =S= 2 ^h * 0 + 2 ^h-1 * 1 + 2 ^h-2 * 2 + ... 2 ⁰ * h

S = 2 ^h {1/2 + 2/2 ² + 3/2 ³ + ... h/2 ^h } --------------------------------------------- 1
Dies istAGPseries, um diese beiden Seiten durch 2 zu lösen
S/2 = 2 ^h {1/2 ² + 2/2 ³ + ... h/2 ^{h + 1} } ----------------------------------------- ---- 2
Subtraktion der Gleichung 2 von 1 ergibt
S/2 = 2 ^h {1/2 + 1/2 ² + 1/2 ³ + ... + 1/2 ^h + h/2 ^{h + 1} }
S = 2 ^{h + 1} {1/2 + 1/2 ² + 1/2 ³ + ... + 1/2 ^h + h/2 ^{h + 1} }
jetzt 1/2 + 1/2 ² + 1/2 ³ + ... + 1/2 ^h sinktGP, dessen Summe kleiner ist als 1 (wenn h zur Unendlichkeit neigt, tendiert die Summe zu 1). Nehmen wir zur weiteren Analyse eine obere Grenze für die Summe von 1 an. 
Dies ergibt S = 2 ^{h + 1} {1 + h/2 ^{h + 1} }
= 2 ^{h + 1} + h
~ 2 ^h + h
as h = log (n) , 2 ^h = n

Daher ist S = n + log (n)
T (C) = O (n)

Nehmen wir an, Sie bauen einen Haufen und gehen von unten nach oben.

1. Sie nehmen jedes Element und vergleichen es mit seinen untergeordneten Elementen, um zu überprüfen, ob das Paar den Heap-Regeln entspricht. Daher werden die Blätter kostenlos in den Haufen aufgenommen. Das liegt daran, dass sie keine Kinder haben. 
2. Nach oben wäre der ungünstigste Fall für den Knoten direkt über den Blättern ein Vergleich (max. Würde mit nur einer Generation von Kindern verglichen)
3. Wenn sie weiter nach oben gehen, können ihre unmittelbaren Eltern maximal mit zwei Generationen von Kindern verglichen werden. 
4. Wenn Sie in derselben Richtung fortfahren, haben Sie im schlimmsten Fall log (n) Vergleiche für die Wurzel. und log (n) -1 für seine unmittelbaren Kinder, log (n) -2 für ihre unmittelbaren Kinder und so weiter.
5. Wenn Sie also alles zusammenfassen, kommen Sie auf etwas wie log (n) + {log (n) -1} * 2 + {log (n) -2} * 4 + ..... + 1 * 2 ^ {( logn) -1} was nichts als O (n) ist. 

Es gibt bereits einige gute Antworten, aber ich möchte eine kleine visuelle Erklärung hinzufügen

Nun schauen Sie sich das Bild an, es gibt
n/2^1grüne Knotenmit Höhe 0 (hier 23/2 = 12)
n/2^2rote Knotenmit Höhe 1 (hier 23/4 = 6)
n/2^3blauer Knotenmit Höhe 2 (hier 23/8 = 3)
n/2^4lila Knotenmit Höhe 3 (hier 23/16 = 2)
so gibt es n/2^(h+1) Knoten für die Höheh
Um die zeitliche Komplexität zu ermitteln, können Sie Menge der geleisteten Arbeitoder max. Anzahl der durchgeführten Iterationenvon jedem Knoten) zählen
Jetzt ist zu bemerken, dass jeder Knoten (höchstens) Iterationen == Höhe des Knotens ausführen kann.

Green = n/2^1 * 0 (no iterations since no children)  
red   = n/2^2 * 1 (*heapify* will perform atmost one swap for each red node)  
blue  = n/2^3 * 2 (*heapify* will perform atmost two swaps for each blue node)  
purple = n/4^3 * 3  

so ist für jedenKnoten mit der Höhe hmaximale geleistete Arbeit n/2 ^ (h + 1) * h

Jetzt ist die gesamte Arbeit erledigt

->(n/2^1 * 0) + (n/2^2 * 1)+ (n/2^3 * 2) + (n/2^4 * 3) +...+ (n/2^(h+1) * h)  
-> n * ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) ) 

jetzt für jeden Wert vonh, die Sequenz

-> ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) ) 

wird niemals 1 überschreiten
Somit wird die Zeitkomplexität niemalsO(n)zum Bauen von Haufen überschreiten

Wenn wir den Haufen bauen, beginnen wir von der Höhe, logn -1 (wobei logn die Baumhöhe von n Elementen ist). Für jedes Element in der Höhe 'h' gehen wir um max.

    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)

Aufeinanderfolgende Einfügungen können beschrieben werden durch: 

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

Durch starre Annäherung n! =~ O(n^(n + O(1))), also T =~ O(nlog(n))

Ich hoffe, das hilft, die optimale Art und Weise, wie O(n) den Build-Heap-Algorithmus für eine gegebene Menge verwendet (Reihenfolge spielt keine Rolle).

Nachweis von O(n)

Der Beweis ist nichts Besonderes, und ziemlich unkompliziert, ich habe nur den Fall eines vollständigen binären Baums bewiesen, das Ergebnis kann für einen vollständigen binären Baum verallgemeinert werden.

@bcorso hat bereits den Beweis der Komplexitätsanalyse bewiesen. Aber für diejenigen, die noch Komplexitätsanalyse lernen, muss ich Folgendes hinzufügen:

Die Grundlage Ihres ursprünglichen Fehlers liegt in einer falschen Interpretation der Bedeutung der Anweisung: "Das Einfügen in einen Heap benötigt O (log n) Zeit". Das Einfügen in einen Heap ist zwar O (log n), aber Sie müssen erkennen, dass n die Größe des Heaps während des Einfügens ist.

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 Heap wie beim Einfügen i ist. Nur die letzte Einfügung hat eine Komplexität von O (log n).

Grundsätzlich wird nur an Nicht-Blatt-Knoten gearbeitet, während ein Heap erstellt wird. Als Arbeit wird der Umfang des Austauschs verwendet, um die Heap-Bedingung zu erfüllen. Mit anderen Worten (im schlimmsten Fall) ist der Umfang proportional zur Höhe des Knotens ... Alles in allem ist die Komplexität des Problems proportional zur Summe der Höhen aller Nicht-Blattknoten. (2 ^ h + 1 - 1) -h-1 = nh-1 = Auf)

Nehmen wir an, Sie haben N Elemente in einem Haufen. Dann wäre seine Höhe Log (N)

Jetzt möchten Sie ein anderes Element einfügen, dann wäre die Komplexität: Log (N), wir müssen den gesamten Weg BIS mit dem Stamm vergleichen.

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

Mit der induction - Technik kann nachgewiesen werden, dass die Komplexität der Einfügung ∑logi wäre. 

Jetzt mit 

log a + log b = log ab

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

welches ist eigentlich O(NlogN)

Aber

wir machen hier etwas falsch, da wir in allen Fällen nicht an die Spitze gelangen. Daher werden wir bei der Ausführung meistens feststellen, dass wir nicht einmal die Hälfte des Baumes erreichen. Daher kann diese Schranke unter Verwendung der in den obigen Antworten angegebenen Mathematik für eine weitere engere Schranke optimiert werden.

Diese Erkenntnis kam mir jedoch nach einem Detail und Experimenten an Heaps.

Ich mag Erklärungen von Jeremy West sehr gerne ... ein anderer Ansatz, der für das Verständnis sehr einfach ist, wird hier angegeben http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity

da die Verwendung von Buildheap von Heapify abhängt, wird ein Shiftdown-Ansatz verwendet, der von der Summe der Höhen aller Knoten abhängt. Also, um die Summe der Höhe der Knoten zu finden, die durch S = Summation von i = 0 bis i = h von (2 ^ i * (hi)) gegeben ist, wobei h = logn die Höhe der Baumlösung s ist, erhalten wir s = 2 ^ (h + 1) - 1 - (h + 1), da n = 2 ^ (h + 1) - 1 s = n - h - 1 = n - logn - 1 s = O (n), und so ist die Komplexität von buildheap O (n).

"Die lineare Zeitbegrenzung von build Heap kann durch Berechnen der Summe der Höhen aller Knoten im Heap angezeigt werden. Dies ist die maximale Anzahl von gestrichelten Linien .. _ 2 ^ (h + 1) - 1 Knoten, die Summe der Höhen der Knoten ist N - H - 1 . Es ist also O (N). "