Exponentielle Laufzeit zeigen

Bitte aktiviere JavaScript!
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:
A

Anzeige




Schau mal hier —> (hier klicken)
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.
 
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
 
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:)
 
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).
 
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.
 
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.
 
A

Anzeige




Vielleicht hilft dir das hier weiter: (klicke hier)
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben