0 Daumen
985 Aufrufe
Bild Mathematik

Ich glaube diese Reihen sind höchstens 1 Schritt oder?
\( function \quad Simple(n) \\  \quad if \quad n ≤ 1  \quad then \\  \quad \quad return \quad 1 \\  \quad else \\  \quad  \quad return \quad n · Simple(n - 1) \\  \quad end \quad if \\ end \quad function \\ \)
Beträgt die Laufzeit hier nn?
\(function \quad Complex(n) \\  \quad m←1 \\  \quad for  \quad i ∈\left\{ 1,...,n \right\} \quad do \\  \quad  \quad m←2 · m \\  \quad   end \quad for \\  \quad s←0 \\  \quad for \quad i ∈ \left\{ 1,...,m \right\} do \\  \quad  \quad s←s + Simple(i) \\  \quad end \quad for \\  \quad return \quad s \\ end \quad function \)

Und was genau ist denn mit m←1 gemeint? Für m wird 1 gesetzt oder?

Könnte jemand bitte helfen? Wir haben weder in der Vorlesung, noch in den Folien dieses Thema so kompliziert durchgenommen.
Avatar von

Deine Funktion Simple berechnet n!

Sie ruft sich selbst wieder auf, ist aber nach n Durchläufen durch IF fertig.

Bsp.

Eingabe 1 kommt zu if  und dort dann als 1 raus.

Bsp.

Eingabe 5 kommt zu 5*Simple(4)

nächster Durchlauf wieder else 4 * Simple(3)

nächster Durchlauf wieder else 3 * Simple(2)


nächster Durchlauf wieder else 2 * Simple(1)

nächster Durchlauf : Fall if    : Ausgabe 1.

Insgesamt Simple(5) = 1*2*3*4*5= 5!


Und bei der Zeile s ← s + Simple(i), wird quasi die Fakultät von i zu dem Wert von s addiert?

Bei der Funktion Complex(n) komme ich auf eine Laufzeit von O(n·2n)

Kann das stimmen? :)

Auch ich komme auf O(n·2n).

Wäre dann die gesammte Laufzeit O(n!*n·2n)? Oder wäre sie O(n!+n·2n)?

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community