Probeklausur Aufgabe 3 - Amortisierte Analyse

Archiv Komplexität von Algorithmen
1

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.

2

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.

3

Hallo,

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?

4

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?

5

Habt ihr denn eine Potentialmethode gefunden? Hatte die Aufgabe bei der Übung falsch und mir notiert, dass

pot(onlyInFront, onlyInBack, inBothEnds) = onlyInFront + onlyInBack

ist. Allerdings geht das kaputt, wenn man z.B. popFront aufruft und onlyInFront = 0, sowie inBothEnds = 0, denn:

pot(0, onlyInBack, 0) - pot(0, 0, onlyInBack) + |onlyInBack| = onlyInBack != konstant

Daher wäre meine Idee jetzt gewesen, in der Funktion selbst eine Fallunterscheidung vorzunehmen, also dass

                                                                 2* inBothEnds,   falls onlyInBack = 0 und onlyInFront = 0
pot(onlyInFront, onlyInBack, inBothEnds) = {
                                                                 onlyInFront + onlyInBack,   sonst

Kann das stimmen, oder mache ich schon wieder einen Fehler?

6

Die Formel für die amortisierte Zeit lautet doch

pot_nachher - pot_vorher + T_genpop

Und damit:

pot(0, 0, onlyInBack) - pot(0, onlyInBack, 0) + |onlyInBack| = -onlyInBack + onlyInBack = 0 = konstant
7

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.

8

Danke für die Antwort, das habe ich so dermaßen konsequent falsch gemacht, dass es mir nicht auffiel :wink: 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).

9

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 :wink:

10

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 :wink:

11

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.

12

Sei mal mit Satzzeichen nicht so geizig - das kann man ja kaum lesen :wink:

13

okay beim nächsten mal! Hast du es trotzdem verstehen können?

14

Erstmal: Siehe auch Lösung von MiriTheRing, dort von bulsa verlinkt.

Was würde denn eigentlich dagegen sprechen, die pot-Funktion auf [m]onlyInBack[/m] zu beschränken, da sich [m]onlyInFront[/m] doch immer wegkürzt?

15

onlyInFront braucht man aber bei popBack (das eben analog funktioniert, nur dass die Aufgabe von onlyInFront und onlyInBack getauscht wurde)

1 „Gefällt mir“
16

Wie bastelt man sich denn generell seine Potentialfunktion?

1 „Gefällt mir“
17

Und warum kann ich für eine andere Methode keine andere pot-Funktion nehmen? Sprich einmal onlyInBack und einmal onlyInFront

18 
// 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!

19

Würde dann nicht mit diesen Potentialfunktionen op1 amortisierte Laufzeit O(j) und op2 O(i) haben? Wie kommst du auf die konstante Laufzeit?

20

Habe eine Invariante hinzugefügt. Jetzt klarer?