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.
eulerscheZahl
tatsächlich wird die Zahl der Durchläufe darunter liegen (weil div den Kommateil ignoriert). Das ist eine Obergrenze.
ubik
Eine Frage hätte ich noch.
Wie schreibt man denn n * (3/4)^Durchläufe = 1 als Logarithmus?
ubik
Ahh!
Vielen Dank.
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.
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.
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
procedure p(n : integer) : integer;
begin
if n < 1 then return 1
else return q(n div 4)
end if
end
procedure q(n : integer) : integer;
begin
if n < 1 then return 1
else return p(n * 3)
end if
end