Probeklausur Aufgabe 3 - Amortisierte Analyse


Ja jetzt macht das Sinn, wenn ich immer bei swap so tausche, dass i bzw j dann 0 wird :slight_smile:


Als „Heuristik“ für die Klausur würde ich sagen: Du hast 2 Funktionen, die nicht in konstanter Zeit laufen sondern c * |onlyInFront| bzw. c * |onlyInBack| Zeit benötigen. Also würde ich genau die 2 Variablen, multipliziert mit der Konstante, in meine Potenzialfunktion packen und per Addition verknüpfen. Wenn du nur die Hälfte der Elemente trotz vollem Aufwand wegnehmen würdest, brauchst du wohl noch irgendwo einen Faktor. Ich glaub nicht, dass es viel schlimmer wird.

2 Likes

Du schaust einfach auf welche(r) Datenstruktur(en) gearbeitet wird und analysierst dann, wie sich diese ändert, wenn du Methodenaufrufe machst.