Worst-Case-Laufzeiten möglichst gut im O-Kalkül abschätzen.

Question

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 if
end function
function 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 function


Ansatz/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 nⁿ?
\(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?

Comments

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·2ⁿ)

Kann das stimmen? :)

---

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

---

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