Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Probeklausur Aufgabe 3 - Amortisierte Analyse
Hi zusammen,
ich bin hier bei ein paar Details unsicher.
zu a):
Hier steht ja wir sollen nur die Laufzeit der oeffentlichen Methoden betrachten, wenn ich das richtig verstehe, braucht man also die Laufzeit von genpop nicht abschaetzen oder?
Ich wuerde also unter der Annahme, dass alle arithmetische Operationen, Vergleiche, Zuweisungen, Assertions, sowie die Stackoperationen pop und push als primitive Operationen mit konstanter Laufzeit behandelt werden auf folgendes kommen:
T_pushFront(n) = T_push + T_inc = \Omega(1)
T_pushBack(n) = T_push + T_inc = \Omega(1)
T_popFront(n) = T_assert + 2T_assign + T_genPop(n) = \Omega(T_genPop(n))
T_popBack(n) = T_assert + 2T_assign + T_genPop(n) = \Omega(T_genPop(n))
Wobei ja relativ offensichtlich ist, dass
T_genPop(n) = O(n)
zu b):
Ich haette hier ein Problem mit der Laufzeit von “make copy of”. Als Kommentar steht zwar O(|thisEnd|) aber wenn ich mit der Potentialmethode beweisen will, dass A_popBack(n) \in O(1) und A_popFront(n) \in O(1), muss ich ja mit der exakten Laufzeit rechnen um mein Potential entsprechend anzupassen. So wie ich das sehe bleibt einem also nichts anderes uebrig als die Laufzeit von “make copy of” auf eine beliebige Funktion f(n) \in O(n) festzulegen um dann die Amortisierte Analyse durchfuehren zu koennen.
ich hab mir c als supremum von ({alle stack funktionen, + - } u {T(make copy of s) / |s| : s in Stack}) definiert und dann gehofft, dass stack funktionen alle o(1) sind und dann in abhänigkeit von c gerechnet.
ist es eigentlich ok, wenn die amortisierte zeit von pop* in einem Fall konstant negativ ist, solange T_am(push, pop) positiv ist?
und ist der algorithmus nicht kaputt, wenn im Kopf von genPop onlyInOtherEnd nicht als referenz übergeben wird?
Ich hab dazu auch noch ne Frage: Wenn ich bei der b dann die amortisierte Laufzeit angeben soll, muss ich das bei der Funktion popFront dann z.B. nur für den worst-case Fall machen, also dass onlyInThisEnd und inBothEnds Null sind oder muss ich dort das für alle Fälle hinschreiben, also einmal wenn onlyInThisEnd>0 ist usw?
Vorsicht, bei der amortisierten Analyse muss man die “genauen” Kosten betrachten (Anzahl primitiver Operationen), die man natürlich in Blöcken einfach zu Konstanten abschätzen kann.
Danke für die Antwort, das habe ich so dermaßen konsequent falsch gemacht, dass es mir nicht auffiel Also dann funktioniert anscheinend doch
pot(...) = onlyInBack + onlyInFront
Okay, ich denke aber nicht, dass das zu schlimm ist, wenn man das etwas schlampig hält, oder? Wie ist es eigentlich, wenn man eine 0 oder negative Zahl als Ergebnis erhält? (kann sein, dass die Frage schon gestellt wurde, aber ich habe noch keine Antwort darauf gefunden) Ist ja eigentlich auch eine Konstante und eigentlich auch in O(1).
Eben genau das kann hier sehr wohl weh tun! Wenn du 0 als Ergebnis erhältst ist das ein sehr sicheres Zeichen für Schlamperei, denn das würde heißen, dass dich beliebig viele Aufrufe der entsprechenden Funktion in der Summe höchstens konstant viel Aufwand kosten, das kann ja wohl nicht sein
Also ist die benötigte Zeit nicht einfach |onlyInBack| in diesem Falle, sondern eher |onlyInBack| + alle Operationen, die vor der Kopie noch passieren (was man jetzt alles wieder als Operation ansieht, sei dahingestellt und ist vermutlich irrelevant). Dann passt das oben auch.
Und wie sieht es aus, wenn man auf negative Werte kommt? Hat man dann auch etwas kaputt gemacht? Bei der 0 kann ich ja noch verstehen, dass nichts zahlen nicht sein kann, aber negative Ergebnisse könnte ja durch irgendeinen Trick doch wieder passen
mir wurde folgendes gesagt, als Potentialfunktion nimmt man c*(onlyInFront+onlyInBack) wobei man c so wählt, dass dieses c gleich der Konstante ist die man erhält wenn man die worstcase Laufzeit von genpop nimmt und man da ja O(size) erhält also hätte man da dann als tatsächliche Laufzeit c*size und dieses c nimmt man.
// invariant i==0 || j==0
int i=0, j=0;
void inc() {
if(i) ++i;
else ++j;
}
void op1() {
if(i) {
[...] // O(i), verändert weder i noch j
swap(i,j);
}
}
void op2() {
if(j) {
[...] // O(j), verändert weder i noch j
swap(i,j);
}
}
Potentialfunktion für op1: i, für op2: j
Wäre das zulässig würden jetzt sowohl op1 als auch op2 in amortisiert konstanter Zeit laufen, tun sie aber nicht!