Exponentielle Laufzeit zeigen

hallowelt543

Mitglied
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 !!!:)
 
Zuletzt bearbeitet:

mihe7

Top Contributor
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.
 
X

Xyz1

Gast
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

Mitglied
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

Top Contributor
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:
Code:
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

Mitglied
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

Top Contributor
ich ja per vollständiger Induktion zeigen müsste, dass n(k)>2n(k-1) gilt oder?
Wozu? Das wurde ja direkt gezeigt.

Ich frag mich nur, wie ich daraus schließe, dass es exponentiell ist.
Indem Du daraus eine nicht-rekursive Behauptung ableitest:
Code:
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
Code:
n(k) > 2^k falls k > 1
Jetzt bist Du mit dem Beweis dran.
 

Neue Themen


Oben