Mission 02

Zwei Runden.
Wie teuer?

02 / 17

Dein Auftrag

Übersetze zuerst genau n = n->next. Danach läufst du mit dem Zeiger durch eine Mini-Liste und leitest Best, Mittel und Worst Case ab.

Du brauchst noch kein C++. Denk an einen Finger, der von Box zu Box wandert.

node* n = head;
while (n != nullptr) {
    if (n->wert >= 0) wert1 += n->wert;
    n = n->next;
}
n = head;
while (n != nullptr) {
    if (n->wert < 0) wert2 += n->wert;
    n = n->next;
}
return wert1 >= -wert2;

Den Pfeil entschärfen

n = n->next bedeutet …

-> greift auf ein Feld der aktuellen Box zu. Das Feld next enthält die Adresse der nächsten Box.

Den Zeiger laufen lassen

Liste: head → 4 → −7 → 2 → nullptr. Drücke „ein Schritt“ und beobachte, was ein Schleifendurchlauf wirklich kostet.

4next →
−7next →
2next →
nullptr

Erst den Pfeil oben korrekt übersetzen.

Pro Box passieren nur Prüfung, eventuell Addition und Zeigerbewegung: konstant viele Operationen. Entscheidend ist, wie viele Boxen besucht werden.

Laufzeit festnageln

Die Liste habe k Knoten. Welche Aussage passt für die gegebene Funktion?

Prüfungsabschluss

Erst nach deinem eigenen Ein-Schleifen-Versuch freigeschaltet.

Musterweg

Jede der beiden Schleifen besucht alle k Knoten – unabhängig von den Werten. Also k + k = 2k Besuche und damit in Best-, Mittel- und Worst Case Θ(k) (folglich auch O(k)).

int summe = 0;
node* n = head;
while (n != nullptr) {
    summe += n->wert;
    n = n->next;
}
return summe >= 0;

Warum gleich? wert1 >= -wert2 ist äquivalent zu wert1 + wert2 >= 0. Die Nullwerte ändern keine Summe.

Kannst du den Pfeil und die zwei vollständigen Durchläufe jetzt begründen?

Noch nicht markiert.