Blatt #5, Aufgaben 2 und 5

[Rocco Rutte]

Hi,

ich habe jetzt einfach zu lange an den Formulierungen gerätselt, als
dass ich es eisern allein weiter versuchen will.

Aufgabe 2: ich komme einfach nicht drauf, wie ich zwei Polynome
möglichst schnell addiere. Ich mache das jetzt mit einem Array, d.h.
Komplexität ist O(n), wobei n der Grad des höherwertigen der beiden
Polynome ist. Unter dem Strich also ein Bucket Sort (oder Count Sort
oder wie es heute gerade heisst). Ich könnte jetzt natürlich das ganze
alternativ mit einer Liste und einer Art Insertion Sort lösen, was aber
den Nachteil hat, das man beim Addieren ständig nach Exponenten suchen
muss. Hat jemand eine Ahnung, was "möglichst schnell" genau bedeuten
soll?

Aufgabe 5: die Sache mit O(nk log k) kriege ich nicht hin. Das "kn" kann
man ja schnell ausrechnen. Aber das log(k) verstehe ich nicht, weil nach
Knuth und Bronstein sowie meiner bescheidenen Logik nach die Höhe eines
k-ären Baumes mit n Knoten größer gleich log_k (n) sein muss. Wenn man
darauf das O-Kalkül anwendet also log(n) statt log(k). Ist das ein
Druckfehler oder habe ich etwas übersehen?

bye, Rocco

[Dirk Lehmann]

Post by Rocco Rutte
Aufgabe 5: die Sache mit O(nk log k) kriege ich nicht hin. Das "kn" kann
man ja schnell ausrechnen. Aber das log(k) verstehe ich nicht, weil nach
Knuth und Bronstein sowie meiner bescheidenen Logik nach die Höhe eines
k-ären Baumes mit n Knoten größer gleich log_k (n) sein muss. Wenn man
darauf das O-Kalkül anwendet also log(n) statt log(k). Ist das ein
Druckfehler oder habe ich etwas übersehen?

Hi Rocco,

ich habe mir da folgendes überlegt:

1. Ich füge erstmal von jeden der k Listen das erste Element in einen Heap,
was glaube ich einen Aufwand von O(k log k) hat.
2. Ich wieder hole das ganze n mal.
3. Dann mach ich einmal heapSort() O(n*k)

Und wenn man alles zusammen rechnet und ein wenig sich das so hinschiebt,
dass es passt, dann kommt man irgendwie auf einen Aufawand von A(n, k) =
n*k(1 + log k). Die eins fliegt raus und man erhält O(n*k log k) ;) ... In
wie fern das allersdings richtig ist, da habe ich keine Ahnung

Und zu der 2. Aufgabe:
Also ich möchte mal denjenigen sehen, der ein so langes Polynom addiert,
dass man da eine Komplexitätsbetrachtung machen muss ;)

Aber ich habe einen Datentyp erstellt, der ein k und ein n (für nx^k)
enthält. Das Polynom wurde dargestellt als Array des Datentyps. Den Trick
den ich genutzt habe, war, dass beim Konstruktoraufruf des Polynoms das rein
gegebene Array gleich sortiert wird (modifiziertes insertSort: Wenn ein
Exponnent mehrfach vorkommt, dann wird dieser gleich drauf addiert). Und
wenn ich addieren will, dann nutze ich die selbe mehtode ;) Somit liegt der
Aufwand nicht mehr in der Addition, sondern im erstellen es Polynoms...

CU Dirk.

[Rocco Rutte]

[...]

"Wer lesen kann ist klar im Vorteil". Oh mann ist das traurig. Ich bin
die ganze Zeit davon ausgegangen, dass wir ein MergeSort entwerfen
sollen, was mit k statt mit 2 Listen arbeitet. Deswegen bin ich ja auch
nicht damit klargekommen, dass O(n*k*log (n)) mit k=2 nicht n*log(n)
ergibt sondern O(n). Wenn man nur das Mischen betrachtet dann stimmt es
wieder. Oh gott ist das peinlich ;-)

Post by Dirk Lehmann
Also ich möchte mal denjenigen sehen, der ein so langes Polynom addiert,
dass man da eine Komplexitätsbetrachtung machen muss ;)

Es muss ja nicht lang sein, es können ja auch u.U. sehr viele sein.

bye, Rocco

[Rocco Rutte]

Post by Dirk Lehmann
1. Ich füge erstmal von jeden der k Listen das erste Element in einen Heap,
was glaube ich einen Aufwand von O(k log k) hat.
2. Ich wieder hole das ganze n mal.
3. Dann mach ich einmal heapSort() O(n*k)

Eigentlich brauchst du HeapSort nicht und wenn du k*n Elemente im Heap
hast, dann hast du mehr als O(k log k).

Ich habe mir jetzt in Ruhe folgendes überlegt:

1. ich nehme die ersten k Elemente in einen Heap -> O(k log k)
2. ich nehme aus dem Heap das Minimum und füge es ans Ende des
sortierten Bereichs -> O(1)
3. POT wiederherstellen -> O(log k)
4. Element aus der Liste in Heap einfügen, aus dem das entnommene
Minimum stammte -> O(log k)
5. weiter mit 2. und zwar n*k mal, also für alle

Wenn man das zusammen rechnet kommt man auf O(n k log k), weil zu keinem
Zeitpunkt mehr als k Elemente im Heap sind.

bye, Rocco

[Dirk Lehmann]

Post by Rocco Rutte
Eigentlich brauchst du HeapSort nicht und wenn du k*n Elemente im Heap
hast, dann hast du mehr als O(k log k).

Stimmt, ich hatte vergessen, dass im HeapSort() noch heapify() drin ist...

Post by Rocco Rutte
1. ich nehme die ersten k Elemente in einen Heap -> O(k log k)
2. ich nehme aus dem Heap das Minimum und füge es ans Ende des
sortierten Bereichs -> O(1)
3. POT wiederherstellen -> O(log k)
4. Element aus der Liste in Heap einfügen, aus dem das entnommene
Minimum stammte -> O(log k)
5. weiter mit 2. und zwar n*k mal, also für alle

Die Implementierung dürfte aber kompliziert werden, da ich schon drei
Iterationsschritte vor Abbruch wissen muss, dass die Iteration in drei
Schritten abbricht. In diesen Fall dürfen die Elemente in (2./4.) ja nicht
mehr getauscht werden, wenn ich das richtig verstanden habe.

Aber sonst ist der Algorithmus besser bzw. vom Aufwand schneller als meiner
;)

CU Dirk.

[Dirk Lehmann]

Post by Dirk Lehmann
Die Implementierung dürfte aber kompliziert werden, da ich schon drei
Iterationsschritte vor Abbruch wissen muss, dass die Iteration in drei
Schritten abbricht. In diesen Fall dürfen die Elemente in (2./4.) ja nicht
mehr getauscht werden, wenn ich das richtig verstanden habe.

Die Implementierung dürfte aber kompliziert werden, da ich schon "k"
Iterationsschritte vor Abbruch wissen muss, dass die Iteration in "k"
Schritten abbricht. In diesen Fall dürfen die Elemente in (2./4.) ja nicht
mehr getauscht werden, wenn ich das richtig verstanden habe.

[Rocco Rutte]

Post by Dirk Lehmann
Die Implementierung dürfte aber kompliziert werden, da ich schon "k"
Iterationsschritte vor Abbruch wissen muss, dass die Iteration in "k"
Schritten abbricht. In diesen Fall dürfen die Elemente in (2./4.) ja nicht
mehr getauscht werden, wenn ich das richtig verstanden habe.

Man kann sowas prima in O(1) zählen. Es würde dann zwar langsamer aber
es beeinflusst die Komplexitätsklasse nicht.

Davon aber mal abgesehen setzt man bei so einem Entwurf natürlich einen
funktionieren Heap voraus (bzw. die Implementierung) und man macht
selbst noch ein paar mehr Optimierungen bzw. kümmert sich erst bei der
Implementierung um die Details...

Und weil ich diesmal gelesen habe: Es ist ja _keine_ Implementierung
gefragt (obwohl es mit dem BinaryHeap von Uebung 4 wohl in ein paar
Minuten getan wäre)... ;-)

bye, Rocco