Laufzeit T(n) bei rekursiven Prozeduren |
10.04.2015, 16:58 | Auf diesen Beitrag antworten » | ||||||||||
ubik | Laufzeit T(n) bei rekursiven Prozeduren Meine Frage: Hallo, die Aufgabe lautet: Geben Sie an, welche Laufzeitkomplexität die folgende Prozedur p in Abhängigkeit von n hat. Begründen Sie Ihre Antwort.
Meine Ideen: Ich habe mir folgendes gedacht:
Kann man das irgendwie noch weiter zusammenfassen? |
||||||||||
|
|||||||||||
10.04.2015, 19:45 | Auf diesen Beitrag antworten » | ||||||||||
eulerscheZahl | Mal eine Überlegung: bei einem Durchlauf (Abarbeitung von p und q) wird n mit 3/4 multipliziert (so in etwa, kann auch weniger sein, wegen div). Wenn wir mit mehreren Durchläufen auf 1 kommen willen, haben wir also: Wenn du das nach der Zahl der Durchläufe umstellst, wirst du zu einer logarithmischen Laufzeit kommen. |
||||||||||
10.04.2015, 19:53 | Auf diesen Beitrag antworten » | ||||||||||
ubik | Ahh! Vielen Dank. |
||||||||||
12.04.2015, 08:54 | Auf diesen Beitrag antworten » | ||||||||||
ubik | Eine Frage hätte ich noch. Wie schreibt man denn n * (3/4)^Durchläufe = 1 als Logarithmus? |
||||||||||
Anzeige | |||||||||||
|
|||||||||||
12.04.2015, 09:50 | Auf diesen Beitrag antworten » | ||||||||||
eulerscheZahl | tatsächlich wird die Zahl der Durchläufe darunter liegen (weil div den Kommateil ignoriert). Das ist eine Obergrenze. |
||||||||||
12.04.2015, 17:31 | Auf diesen Beitrag antworten » | ||||||||||
ubik | Hallo, muss das nicht d = ln(1/n) / ln(4/3) d = -ln(n) / ln(4/3) heißen? Da ja ln (1/n) = - ln(n) ist? Dann kann ich mir irgendwie nicht vorstellen, wie die Anzahl der Durchläufe negativ sein kann Edit: Ah ne, alles klar, das Minus wird zu Plus, wenn ich ln(4/3) benutze. |
|