Komplexitätsklassen bei Algorithmen?
Servus,
ich verstehe einfach nicht, wie ich mir die Berechnung der O-Notation von folgender "Funktion" erschließen kann:
Ich schätz mal O(1) ist der "y := x" Teil. Aber alles danach versteh ich einfach nicht xD
Wäre nett, wenn ich mir jemand weiterhelfen können.
Danke im Voraus!
2 Antworten
Grundsätzlich steht in dem Text, wie hier die Regel ist: Bei einer if-Abfrage nehmen wir das Maximum aus dem "if-Block " und dem "else-Block " und addieren den Aufwand für den Test. Gehen wir die erste Zeile durch.
Das erste O(1) kommt aus dem Test x > 100.
In dem max steht das O(1) dann für die Zuweisung y := x, weil die ja in konstanter Zeit machbar ist bzw. nicht von n abhängt. Das zweite Argument ist dann für den else Block:
Hier haben wir eine for Schleife, die von 1 bis n läuft, also lineare Zeit braucht und in dieser for Schleife haben wir wieder eine If-Verzweigung, bei der wir vorgehen können, wie bei der ersten. Da es hier keinen else Block gibt, ist das zweite Argument 0. Der Rest ist umformen.
Macht das Sinn?
Danke! Mir war das mit dem Max() nicht klar, deshalb hab ich die verschiedenen Aussagen nicht verstanden.
Ich versuche es mal so zu visualisieren:
O(1) + max( O(1), n*(O(1)+max(O(1),0)))
A B C D E
if x > 100 => A
y:=x => B
else
for i:=1 to n => n*
if a[i] > y => C
y:=x => D
[else] => E