Laufzeitanalyse

Krachi

Hi!

Ich möchte bei den folgenden Algorithmen die Laufzeit mittels O-Notation bestimmen:

1 int Pow1(int n) 
2 { 
3 if (n > 0) { 
4 return (2*Pow1(n-1)); 
5 } 
6 else { 
7 return 1; 
8 } 
9 }

Sowie

1 int Pow2(int n) 
2 { 
3 if (n > 0){ 
4 return (Pow2(n-1) + Pow2(n-1)); 
5 } 
6 else { 
7 return 1; 
8 } 
9 }

Wenn ich das richtig sehe, dann berechnen beide ganzzahlige Vielfache von 2. Außerdem müssten die Laufzeiten übereinstimmen.
Es handelt sich meiner Meinung nach um rekursive Algorithmen, die sich dann selber aufrufen.

Die Laufzeit müsste O(n) betragen und damit linear sein. Ich bin mir aber nicht sicher.

icarus2

Der erste Algorithmus hat Laufzeit $\mathcal{O}(n)$ , das ist richtig.

Aber der zweite Algorithmus hat Laufzeit $\mathcal{O}(2^n)$ .

Krachi

Warum das?

icarus2

Krachi schrieb:

Warum das?

Jedes Mal wenn du Pow2 ausfuerst (ausser wenn n = 0), dann rufst du die Methode 2 Mal rekursiv auf.
Du hast
Pow2(n) --> Pow2(n-1) + Pow2(n-1) --> (Pow2(n-2) + Pow2(n-2)) + (Pow2(n-2) + Pow2(n-2)) --> ...

Das heisst bei jedem Durchlauf von Pow2 verdoppelt sich die Anzahl der rekursiven Aufrufe. Wenn du $n$ mal verdoppelst, dann hast du am Ende $2^n$ .

*Edit
Etwas formaler: Sei $T(n)$ die Laufzeit deines Algorithmus. Dann gilt (wenn $n = 0$ , dann gibts du eifach $1$ zurück was konstante Laufzeit hat. Ansosten rufst du deine Funtion zwei Mal rekursiv auf mit $n - 1$ )

$T(n) = \begin{cases} 1&\quad ,n = 0\\ 2 \cdot T(n-1)&\quad ,n \geq 1 \end{cases}$

Wenn du diese Rekursionsgleichung auflöst wirst du sehen, dass $T(n) = \mathcal{O}(2^n)$ .