Leiten Sie die Laufzeit/Kostenfunktion des folgenden Algorithmus für ein Array der Länge n>2 her.
- Gewertet werden nur Feldzugriffe.
- Überlegen Sie zunächst, für welche Eingaben jeweils der Best Case und der Worst Case eintritt.
- Gehen Sie bottom-up vor, d.h. berechnen Sie zunächst die Schritte der Funktion unicorn_ninja() in Abhängigkeit von pos. Betrachten Sie zunächst nur den Best Case.
- Berechnen Sie nun die Schritte für das Gesamtverfahren $a^{best}(n)$, indem Sie die Schritte der Schleifendurchläufe aufsummieren.
- Wiederholen Sie zuletzt die Herleitung für den Worst Case. Leiten Sie auch hier eine Formel für die Laufzeit $a^{worst}(n)$ her, diese müssen Sie aber nicht weiter vereinfachen.
# Gegeben: Ein Array a der Länge n>2.
pos = 0
result = 0
while pos<n:
result += unicorn_ninja(a, pos, a[pos])
pos += 1
return result
# Hilfsfunktion
function unicorn_ninja(a, pos, val):
i = pos
while i >= 0 and a[i] >= val:
i -= 2
return i