heapsort
-
hallo,
hab grade bei wikipedia gelesen dass man einen heap mit O(n) bauen kann.
wenn ich n-Elemente habe muss ich den heap doch n mal bauen.
Nach meiner Rechnung ergibt das dann O(n*n).Aber tatsächlich ist es ja O(n*log n ) . Wo lieg ich falsch ?
-
Die Sortierung dauert O(n*log n), der Speicherverbrauch jedoch nur O(n).
-
blurry333 schrieb:
hallo,
hab grade bei wikipedia gelesen dass man einen heap mit O(n) bauen kann.
wenn ich n-Elemente habe muss ich den heap doch n mal bauen.
Nach meiner Rechnung ergibt das dann O(n*n).Aber tatsächlich ist es ja O(n*log n ) . Wo lieg ich falsch ?
Aufbauen kannst du den Heap tatsaechlich in O(N). Anschliessend musst du N mal das groesste/kleinste Element entfernen O(1) und nachher die Heapordnung wieder herstellen O(log N).
Ergibt in Summe O(N) + N*(O(1) + O(log N)) = O(N * log N)(EDIT: Klammer)
-
blurry333 schrieb:
hallo,
hab grade bei wikipedia gelesen dass man einen heap mit O(n) bauen kann.
wenn ich n-Elemente habe muss ich den heap doch n mal bauen.
Nach meiner Rechnung ergibt das dann O(n*n).Aber tatsächlich ist es ja O(n*log(n)) . Wo lieg ich falsch ?
Du musst, nachdem du den Heap gemacht hast, n mal ein Element nach unten wandern lassen. Dieses Element wandert ungefähr O(log(n)) mal (weil es ja ein Baum ist).
Also: n * O(log n) -> O(n * log(n))
-
Ist eigentlich der linke Kindknote größer als der rechte ?
z.B.
9
/ \
1 7
-
blurry333 schrieb:
Ist eigentlich der linke Kindknote größer als der rechte ?
z.B.9 / \ 1 7Nö, gar nicht nötig.
-
hmm,
aber so muss ich ja immer beide Kindknoten vergleichen.
Wenn ich wüßte dass der linke größer ist , wäre es doch irgendwie einfacher ?
-
Aber die offizielle Heap Definition sieht das ja auch nicht vor,
dass der linke Sohn größer sein muss als der rechte.Was bedeutet eigentlich Zeitkomplexität.
Was beinhaltet das alles ? Neben Kopieraufwand auch Vergleiche ?
-
blurry333 schrieb:
Was bedeutet eigentlich Zeitkomplexität.
Was beinhaltet das alles ? Neben Kopieraufwand auch Vergleiche ?Ich würde sagen, Operationen.
Ein Introsort mit Binary-Search, die eine Komplexität von O(log n) hat, hat trotzdem O(n²)