Sind die sicher, dass es in O(n log(n)) stattfinden soll? Ich kriege das in O(n) hin…

Ich auch

ich auch :)

Kamt ihr auch so schnell auf den Algorithmus? Hab den sofort gesehen. Ist auch nur ein paar wenige Zeilen lang. Kriege dabei einen "entarteten" Suchbaum. Und wieso gibt es dann satte 3 Punkte dafür?

Für neugierige – könntet ihr die Aufgabe bzw. nen Link darauf posten? ;-)

Naja, so ganz entartet darf er nicht sein. In der E -Mail, die wir über Stine bekommen haben, stand, dass er möglichst ballanciert sein soll. Dadurch wird der Algoritmus aber nur bissel komplizierter.

habs gerade noch mal nachgerechnet. kommt doch n lg n raus, da man für jedes Element im Baum noch nach der richtigen Position suchen muss :)

da man für jedes Element im Baum noch nach der richtigen Position suchen muss :)

versteh ich nicht. welche operation führst du durch, dass du noch f(n) im masterth. kassierst?

jedes Element im Array muss mindestens ein mal angefasst werden. Für jedes Element muss im Baum die Stelle durch vergleiche gefunden werden, an die es gepackt wird - das sind pro Element im schlimmsten fall lg(n) vergleiche, wenn der Baum balanciert ist- also n ln(n) isgesamt.

Naja, so ganz entartet darf er nicht sein. In der E -Mail, die wir über Stine bekommen haben, stand, dass er möglichst ballanciert sein soll. Dadurch wird der Algoritmus aber nur bissel komplizierter.

Ich habe keine E-Mail bekommen… Gar keine…

Edit: Habe gerade mal geguckt. Die haben eine tolle "Stine-Nachricht" verschickt. Die guckt sich doch niemand an! Toll! Habe jetzt das ganze Zeug fertig geschrieben und voll viel Zeit in die Tonne gekloppt. ICH HASSE STINE! Sind die Leute inzwischen nicht mehr fähig, einen Mail-Client zu benutzen? Es gibt doch extra dafür Mailinglisten am IKum.

jedes Element im Array muss mindestens ein mal angefasst werden. Für jedes Element muss im Baum die Stelle durch vergleiche gefunden werden, an die es gepackt wird - das sind pro Element im schlimmsten fall lg(n) vergleiche, wenn der Baum balanciert ist- also n ln(n) isgesamt.

ok, dann haben wir verschiedene algorithmen :)

Sind die sicher, dass es in O(n log(n)) stattfinden soll? Ich kriege das in O(n) hin…

Wo stand denn was von O(n log(n))? Bei mir steht O(n) im Aufgabentext.

Für neugierige – könntet ihr die Aufgabe bzw. nen Link darauf posten? ;-)

Die Aufgabe steht nur in STiNE und zumindest bei den Folienkopien steht extra dabei, dass wir sie keinesfalls irgendwie weiterverbreiten sollen, erst recht nicht online. Ich kann sie aber mal etwas umformulieren:

Im Worst Case kostet das Einfügen von n Elementen in einen BST (Binary Search Tree) O(n^2) Zeit. Wenn die einzufügenden Elemente in sortierter Form vorliegen, lässt sich ein BST in O(n) aufbauen. Geben Sie den Algorithmus dafür in Pseudocode an und erklären Sie ihn.

Ich denke, die von Hackbert gemeinte Lösung ist ziemlich offensichtlich.

Toll! Habe jetzt das ganze Zeug fertig geschrieben und voll viel Zeit in die Tonne gekloppt.

Dito. Hatte aber schon damit gerechnet, dass sie wahrscheinlich eigentlich einen balancierten Suchbaum haben wollten, denn inzwischen hab ich etwas Übung im Hellsehen (zu irgendwas muss AD ja nutze sein). Darum hab ich schon vorm sauberen Abtippen in STiNE geguckt.

jedes Element im Array muss mindestens ein mal angefasst werden. Für jedes Element muss im Baum die Stelle durch vergleiche gefunden werden, an die es gepackt wird - das sind pro Element im schlimmsten fall lg(n) vergleiche, wenn der Baum balanciert ist- also n ln(n) isgesamt.

Es geht aber auch in O(n).

Aha. Darf ich auch fragen wie?

Aha. Darf ich auch fragen wie?

MAGIC AT WORK

Aha. Darf ich auch fragen wie?

Divide & Conquer ist das Stichwort. Die reine Rekursion! Bisschen wie, mal sagen, binäre Suche.

Habe auch mit devide and concer gemacht. Aber zum Einfügen braucht man immer noch lg(n) zeit.

Divide & Conquer ist das Stichwort. Die reine Rekursion! Bisschen wie, mal sagen, binäre Suche.

Divide & Conquer ist das Stichwort. Die reine Rekursion! Bisschen wie, mal sagen, binäre Suche - man Ingo.

$ man Ingo
No manual entry for Ingo

Wie soll ich das jetzt verstehen?

Habe auch mit devide and concer gemacht. Aber zum Einfügen braucht man immer noch lg(n) zeit.

Du kannst ja beim Rekursionsaufruf immer den Knoten mit übergeben an dem eingefügt werden soll. Dann sparst du dir das durchlaufen des Baumes.

$ man Ingo
No manual entry for Ingo

[img]http://www.fb18.de/gfx/7.gif[/img][img]http://www.fb18.de/gfx/7.gif[/img][img]http://www.fb18.de/gfx/7.gif[/img]

Anarch: Wie bekommt man Werte aus einem sortiertem Array in O(n) in einen anfangs leeren BST einsortiert?

Da dort aber nicht steht, dass das ganze balanciert sein muss, hätte es die wohl ziemlich triviale Lösung


gegeben: Array A, mit aufsteigend sortierten Zahlen. parent <- nil for i <- 1 to length(A) do p(A(i)) <- parent right(A(i) <- A(i+1) p(A(i+1)) <- A(i)
wohl auch getan (hier ist es allerdings echt hässlich aufgeschrieben).

Anarch: Wie bekommt man Werte aus einem sortiertem Array in O(n) in einen anfangs leeren BST einsortiert?

Da dort aber nicht steht, dass das ganze balanciert sein muss, hätte es die wohl ziemlich triviale Lösung


gegeben: Array A, mit aufsteigend sortierten Zahlen. parent <- nil for i <- 1 to length(A) do p(A(i)) <- parent right(A(i) <- A(i+1) p(A(i+1)) <- A(i)
wohl auch getan (hier ist es allerdings echt hässlich aufgeschrieben).

Du hast aber die Anmerkungen in Stine gesehen? Es soll ein möglichst balancierter Baum sein…
Möglichst.. ;-) Antwort: Leider war es uns nicht möglich, einen balancierten Baum zu erstellen. Daher haben wir nun nen tollen, langen Baum mit einem langen, schicken, wohlgeformten rechten Ast ;-)

Du hast aber die Anmerkungen in Stine gesehen? Es soll ein möglichst balancierter Baum sein…

Nein, die Anmerkung gab es noch nicht als och das gemacht habe, also kann ich das auch so als Lösung haben. Ich hätte mich sonst auch gerne mit Rarey darüber gestritten.

Wenn dad nichtmal als mail gesendet wird, sehe ich so ein Verhalten nicht ein. Was wäre gewesen wenn ich das alles scon vor der Änderung abgegeben hätte? nochmal na hreichen? aus welchem grund sollte ich dann nochmal in STiNE nachsehen?

jaaaa, ich streite mich gerne mit! Bin dabei ;-)
Stimmt dir da voll zu, nichts destp trotz wird hier mittlerweile eine andere Lösung gefordert, und das haben wir in diesem Thread auch schon festgestellt! Daher meine Anmerkung.