# Exponentielle Laufzeit zeigen



## hallowelt543 (8. Nov 2018)

1 function p1([v_i,...,v_(i+k−1)]);
2 begin
3    if k = 1 then
4      return 0;
5     else if k is even then    //Spieler 1 ist am Zug
6       first_coin ← p1([v_i+1,...,v_(i+k−1)]);
7       last_coin ← p1([v_i,...,v_(i+k−2)]);
8       return f(first_coin , last_coin);  //f ergibt sich aus Ihrer Antwort oben.
9     else                           //Spieler 2 ist am Zug
10      first_coin ← p1([v_(i+1),...,v_(i+k−1)]);
11      last_coin ← p1([v_i,...,v_(i+k−2)]);
12      return g(first_coin , last_coin);  //g ergibt sich aus Ihrer Antwort oben. 
13      end;
14 end;
Ich soll zeigen , dass dieser Alg. exponentielle Laufzeit hat. (Man geht davon aus, dass Funktion g und f in Theta(1) berechnet werden )
Irgendwie ist das für mich schon eindeutig wegen der Rekursion, aber ich weiß nicht wie ich das zeigen soll...
Danke für die Hilfe !!!


----------



## mihe7 (9. Nov 2018)

hallowelt543 hat gesagt.:


> aber ich weiß nicht wie ich das zeigen soll...


Zum Beispiel könntest Du auf die Idee kommen, eine rekursive Funktion anzugeben, die für ein gegebenes k die Zahl der Schritte liefert... Darauf aufbauend könntest Du versucht sein, eine nicht-rekursive Behauptung aufzustellen, die Du vor lauter Übereifer per vollständiger Induktion beweist. Und zu Deiner großen Enttäuschung musst Du dann feststellen, dass es fast nichts mehr zu tun gibt.


----------



## Xyz1 (9. Nov 2018)

Mitm Mastertheorem.


----------



## Xyz1 (9. Nov 2018)

Kann falsch sein:
Spieler 1 und 2 wechseln sich ab
a = 2
n/b = n/(n/(n-1))
T(n/b) = n/1
f(n) = n
=> T(n) = 2*T(n/(n/(n-1)))+n => T(n) = Θ(n^log_(n/(n-1))_2) ~ Θ(n^n)

n^n habe ich, aber n^log_(n/(n-1))_2 ergibt keinen Sinn. Das Mastertheorem kann nicht angewendet werden da n/b = n/1 = n unsinnig ist


----------



## hallowelt543 (10. Nov 2018)

Nochmal eine Frage zum Aufstellen der Rekursionsgleichung:
Bisher hab ich mir folgendes überlegt:
Ist k ungerade kommt Spieler 2 k/2 Mal (aufgerundet dran) und Spieler 1 k/2 abgerundet.
Ist k gerade kommen beide Spieler k/2 Mal dran.

Jetzt ist meine Frage: Wie stelle ich aus diesem Wissen die Rekursionsgleichung auf


----------



## mihe7 (10. Nov 2018)

Zähl einfach die Schritte:
für k = 1 wird das if und das return ausgeführt, das sind zwei Schritte also
`n(k) = 2 falls k = 1`

für k gerade werden die Schritte 3, 5, 6, 7 und 8 ausgeführt.
für k ungerade werden die Schritte 3, 5, 10, 11 und 12 ausgeführt.

Für die Schritte 3, 5, 8 und 12 kann eine Konstante als obere Grenze der Schrittzahl angegeben werden. Die Schritte 6, 7 bzw. 10, 11 rufen die Funktion rekursiv mit jeweils k-1 Elementen auf. Also kann insgesamt gesagt werden:

```
n(k) = 2 falls k = 1
n(k) <= c + n(k-1) + n(k-1) = c + 2n(k-1) falls k > 1
```
Außerdem gilt mit Sicherheit `n(k) > 2n(k-1)`.


----------



## hallowelt543 (10. Nov 2018)

Erstmal danke
Das Problem, was ich jetzt hab, dass ich ja per vollständiger Induktion zeigen müsste, dass n(k)>2n(k-1) gilt oder?
Ich frag mich nur, wie ich daraus schließe, dass es exponentiell ist.


----------



## mihe7 (10. Nov 2018)

hallowelt543 hat gesagt.:


> ich ja per vollständiger Induktion zeigen müsste, dass n(k)>2n(k-1) gilt oder?


Wozu? Das wurde ja direkt gezeigt. 



hallowelt543 hat gesagt.:


> Ich frag mich nur, wie ich daraus schließe, dass es exponentiell ist.


Indem Du daraus eine nicht-rekursive Behauptung ableitest:

```
n(1) = 2
n(2) > 2n(1) = 4
n(3) > 2n(2) > 2(2(n(1)) = 2(2(2))) = 2^3
n(4) > 2n(3) > 2(2(n(2)) = 2(2(2(n(1))) = 2(2(2(2)))) = 2^4
...
```
Es scheint also, als gelte

```
n(k) > 2^k falls k > 1
```
Jetzt bist Du mit dem Beweis dran.


----------



## hallowelt543 (10. Nov 2018)

Achso, danke dir vielmals noch!!!


----------

