Exponentielle Laufzeit zeigen

Diskutiere Exponentielle Laufzeit zeigen im Hausaufgaben Forum; 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...

  1. hallowelt543
    hallowelt543 Neues 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: 8. Nov. 2018
  2. Vielleicht hilft dir dieses Training hier weiter.
  3. mihe7
    mihe7 Bekanntes Mitglied
    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.
     
  4. DerWissende
    DerWissende Bekanntes Mitglied
    Mitm Mastertheorem. ;)
     
  5. DerWissende
    DerWissende Bekanntes Mitglied
    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
     
    mihe7 gefällt das.
  6. hallowelt543
    hallowelt543 Neues 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:)
     
  7. mihe7
    mihe7 Bekanntes Mitglied
    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 (Text):

    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).
     
  8. hallowelt543
    hallowelt543 Neues 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.
     
  9. mihe7
    mihe7 Bekanntes Mitglied
    Wozu? Das wurde ja direkt gezeigt.

    Indem Du daraus eine nicht-rekursive Behauptung ableitest:
    Code (Text):

    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 (Text):

    n(k) > 2^k falls k > 1
     
    Jetzt bist Du mit dem Beweis dran.
     
  10. hallowelt543
    hallowelt543 Neues Mitglied
    Achso, danke dir vielmals noch!!!
     
  11. Wenn du Java lernen möchtest, empfehlen wir dir diese Online-Training hier
Die Seite wird geladen...

Exponentielle Laufzeit zeigen - Ähnliche Themen

exponentielle Kurve
exponentielle Kurve im Forum Mathematik
Exponentielle Verteilung in einer Liste
Exponentielle Verteilung in einer Liste im Forum Allgemeine Java-Themen
Automatisches Methoden Laufzeiten logging?
Automatisches Methoden Laufzeiten logging? im Forum Allgemeine Java-Themen
Objekt Typ zur Laufzeit ermitteln
Objekt Typ zur Laufzeit ermitteln im Forum Java Basics - Anfänger-Themen
Datei im Package zur Laufzeit editieren
Datei im Package zur Laufzeit editieren im Forum Java Basics - Anfänger-Themen
Thema: Exponentielle Laufzeit zeigen