Gegeben:
function \( \operatorname{Simple}(n) \)\(\quad\)if \( n \leq 1 \) then\(\quad\)\(\quad\)\(\quad\)return 1\(\quad\)else\(\quad\)\(\quad\)return \( n \cdot \operatorname{SimplE}(n-1) \)\(\quad\)end ifend functionfunction Complex ( \( n \) )\(\quad\)\( m \leftarrow 1 \)\(\quad\)for \( i \in\{1, \cdots, n\} \) do\(\quad\)\(\quad\)\( m \leftarrow 2 \cdot m \)\(\quad\)end for\(\quad\)\( s \leftarrow 0 \)\(\quad\)for \( i \in\{1, \cdots, m\} \) do\(\quad\)\(\quad\)\( s \leftarrow s+\operatorname{Simple}(i) \)\(\quad\)end for\(\quad\)return \( s \)end functionAnsatz/Problem:
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?
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.
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).
Ein anderes Problem?
Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos