CODE-DETEKTIV
Drei Wege zum Produkt?
04 / 17
Deine Mission
Füttere drei Funktionen mit demselben Array. Finde erst den Unterschied, dann ihre Laufzeiten.
Erster Zug: Wähle unten den Testfall mit einer Null. Was erwartest du?
fun1: wenn a[i] != 0 → prod *= a[i]
fun2: wenn a[i] == 0 → return 0
sonst → prod *= a[i]
fun3: wenn a[i] gerade → addiere prod genau a[i]-mal
sonst → prod *= a[i]Spuren sichern
Klicke einen Beweis-Testfall. Danach tippe auf jede Funktion, um ihren Rückgabewert aufzudecken.
Bei
fun1 wird eine Null übersprungen. Bei fun2 beendet sie die Funktion sofort. Frage bei fun3: Wie oft läuft j < a[i]?res += prod, genau a[i]-mal, bedeutet für positive gerade Werte: prod · a[i]. Bei einer negativen geraden Zahl läuft die Schleife jedoch nullmal.Laufzeit-Tresor
Ordne Best und Worst zu. Der typische Fehlweg „alle haben nur eine äußere Schleife, also Θ(n)“ wird hier geprüft.
Prüfungssatz bauen
Vervollständige die gemeinsame Vorbedingung. Erst ein Versuch entsperrt den Musterweg.
Klausurabschluss
- Ausgabe: fun1 ignoriert Nullen; fun2 und fun3 ergeben bei Null 0. fun3 simuliert bei positiven geraden Werten die Multiplikation durch wiederholte Addition.
- Gemeinsame Vorbedingung: Alle Werte sind ungleich 0 und gerade Werte sind positiv. Die einfache klausurnahe Form lautet: alle Werte sind positiv.
- fun1: Best = Worst = Θ(n), weil jedes der n Elemente geprüft wird.
- fun2: Best = Θ(1) bei erster Null; Worst = Θ(n) ohne Null.
- fun3: Best = Θ(n) bei nur ungeraden Werten. Präzise: Θ(n + Σ positive gerade a[i]). Sind diese Werte O(n), ist der Worst Case Θ(n²); ohne Werteschranke ist der Worst Case nicht allein durch n begrenzt.
PDF-Präzisierung: Die Musterlösung nennt „alle Werte ungleich 0“. Das reicht für negativen geraden Input nicht: Bei -2 läuft j < -2 kein einziges Mal.
Wie sitzt es?
Noch nicht markiert.