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
![](https://images.gutefrage.net/media/default/user/9_nmmslarge.png?v=1551279448000)
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?
![](https://images.gutefrage.net/media/default/user/3_nmmslarge.png?v=1438863662000)
Danke! Mir war das mit dem Max() nicht klar, deshalb hab ich die verschiedenen Aussagen nicht verstanden.
![](https://images.gutefrage.net/media/default/user/11_nmmslarge.png?v=1551279448000)
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
![](https://images.gutefrage.net/media/default/user/3_nmmslarge.png?v=1438863662000)