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 !!!
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: