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ⁿ)?

Answer 1

Antwort mit KI erzeugt

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

Einführung

Um die Worst-Case-Laufzeiten der beiden Funktionen Simple und Complex im O-Kalkül abzuschätzen, analysieren wir zunächst jede Funktion separat und wenden dann auf die Complex Funktion unsere Ergebnisse der Analyse der Simple Funktion an.

Analyse der Funktion Simple

Die Funktion Simple(n) ist eine Rekursive Funktion, die das Produkt aller ganzen Zahlen von \(n\) bis 1 berechnet. Dieses Produkt ist bekannt als die Fakultät von \(n\), symbolisiert durch \(n!\). Die Fakultät wird wie folgt definiert:

- \(0! = 1\)
- Für \(n > 0\), ist \(n! = n \cdot (n-1)!\)

Die Laufzeit dieser Funktion ist proportional zur Anzahl der Rekursionsaufrufe. Da es für jede ganze Zahl \(n\) genau einen Rekursionsaufruf gibt, bis es zu \(n \leq 1\) kommt, beträgt die Laufzeit \(O(n)\), nicht \(n^n\), was eine weit größere und ungenaue Abschätzung wäre.

Analyse der Funktion Complex

Bei der Analyse der Complex Funktion bemerken wir zwei Hauptteile:

1. Erster Teil: Hier wird eine Variable \(m\) mit \(1\) initialisiert und dann in jeder Iteration der Schleife verdoppelt. Nach \(n\) Iterationen würde \(m\) den Wert \(2^n\) haben, da in jeder Iteration \(m\) verdoppelt wird. Dies entspricht einer Laufzeit von \(O(n)\) für den ersten Teil.

2. Zweiter Teil: In der zweiten Schleife hängt die Laufzeitanalyse vom endgültigen Wert von \(m\), also \(2^n\), ab. Innerhalb dieser Schleife wird die Simple(i) Funktion für jeden Wert von \(i\) von \(1\) bis \(m\) aufgerufen. Da Simple(i) eine Laufzeit von \(O(i)\) hat, müssen wir die Laufzeit aller Aufrufe zusammenzählen.

Die Gesamtlaufzeit für den zweiten Teil ist die Summe \(S = \sum_{i=1}^{2^n} O(i)\), was äquivalent zur Summe der ersten \(2^n\) positiven ganzen Zahlen ist und durch die Formel \(S = \frac{2^n(2^n + 1)}{2}\) ausgedrückt werden kann. Dies vereinfacht sich zu \(O(2^n \cdot 2^n)\) oder \(O(4^n)\), was die Laufzeit des zweiten Teils ist.

Zusammenfassung der Laufzeit für Complex

Da die Gesamtlaufzeit der Funktion Complex von dem langsameren Teil abhängt, ist die Worst-Case-Laufzeit \(O(4^n)\) aufgrund des zweiten Teils der Funktion. Der erste Teil der Funktion mit einer Laufzeit von \(O(n)\) wird von der exponentiell langsameren Wachstumsrate des zweiten Teils dominiert.

Zu m←1

Die Notation \(m \leftarrow 1\) bedeutet, dass der Variablen \(m\) der Wert \(1\) zugewiesen wird. Es ist eine Initialisierung von \(m\) mit dem Startwert \(1\), bevor in den Schleifen weitere Operationen mit \(m\) durchgeführt werden.