Zähle die Arbeit, nicht nur die Plätze.
Deine Mission
Beide Maschinen bekommen dasselbe Array. Finde heraus, ob sie dasselbe Ergebnis liefern — und warum ihre Arbeit trotzdem verschieden ist.
Erster Zug: Verändere genau eine Zahl. Beobachte sofort, was mit den Einzelschritten passiert.
fun1: val = val + a[i]
fun2: solange v > 0: val += 1; v -= 1
solange v < 0: val -= 1; v += 1Array unter Strom
Drehe an den drei Werten. fun2 zerlegt jede Zahl in +1- oder −1-Schritte.
v ist nur eine Arbeitskopie von a[i]. Jede Runde bewegt v um genau 1 Richtung 0 — und val um denselben Schritt Richtung a[i].a[i] = −3: v: −3 → −2 → −1 → 0 und gleichzeitig val dreimal −= 1. Netto wird also −3 addiert.Gleiches Ergebnis?
Was gilt für beliebige positive, negative und Null-Werte?
Die n-Falle knacken
Zwei Arrays haben beide n = 3. Welcher Schluss ist korrekt?
[1, 1, 1]fun2: 3 innere Schritte[100, 100, 100]fun2: 300 innere SchrittePrüfungssatz bauen
Wann erwartest du bei fun2 die höhere Laufzeit? Formuliere einen Satz. Erst dein Versuch öffnet den Musterweg.
Klausurabschluss
- Gleiches Ergebnis: Beide berechnen
Σ a[i]. fun2 ersetzt jede Addition vona[i]durch genau|a[i]|viele Schritte von±1. - fun1:
Θ(n), denn jedes der n Elemente verursacht konstant viel Arbeit. - fun2 präzise:
Θ(n + Σ|a[i]|). Große Beträge — positiv oder negativ — erzeugen viele Schleifendurchläufe. - Vergleich: Bei großen Beträgen ist fun2 langsamer; bei durch eine Konstante beschränkten Beträgen sind beide
Θ(n). - Eingabegröße: Nur n ist für fun2 nicht aussagekräftig genug. Passender sind zusätzlich
Σ|a[i]|oder, im üblichen Bitkostenmodell, die Gesamtzahl signifikanter Bits der Werte.
Einordnung zur PDF-Lösung: Die Musterlösung nennt bei festgelegter Eingabegröße n beide Funktionen O(n), weist aber selbst darauf hin, dass die Werte bzw. ihre Bitgrößen als alternative Eingabegröße geeigneter sind. Die wertabhängige Summe macht genau diesen versteckten Aufwand sichtbar.
Wie sitzt es?
Noch nicht markiert.