Informatiker Board | Druckvorschau: Laufzeit T(n) bei rekursiven Prozeduren

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- Laufzeit T(n) bei rekursiven Prozeduren (http://www.informatikerboard.de/board/thread.php?threadid=2216)

Geschrieben von ubik am 10.04.2015 um 16:58:

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

Meine Ideen:
Ich habe mir folgendes gedacht:

code:
1: 2: 3: 4: 5:	T1(n) = { 1, falls n = 1 { T2(n/4), sonst T2(n) = { 1, falls n < 1 { T1(n*3), sonst

Kann man das irgendwie noch weiter zusammenfassen?

Geschrieben von eulerscheZahl am 10.04.2015 um 19:45:

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:
$[latex]n \cdot \left(\frac{3}{4}\right)^\text{Durchläufe}=1[/latex]$
Wenn du das nach der Zahl der Durchläufe umstellst, wirst du zu einer logarithmischen Laufzeit kommen.

Geschrieben von ubik am 10.04.2015 um 19:53:

Ahh!

Vielen Dank.

Geschrieben von ubik am 12.04.2015 um 08:54:

Eine Frage hätte ich noch.

Wie schreibt man denn n * (3/4)^Durchläufe = 1 als Logarithmus?

Geschrieben von eulerscheZahl am 12.04.2015 um 09:50:

$[latex]n \cdot \left(\frac{3}{4}\right)^d=1[/latex]$
$[latex]\left(\frac{3}{4}\right)^d=\frac{1}{n}[/latex]$
$[latex]\ln\left(\left(\frac{3}{4}\right)^d\right)=\ln\left(\frac{1}{n}\right)[/latex]$
$[latex]d \cdot \ln\left(\frac{3}{4}\right)^d=\ln\left(\frac{1}{n}\right)[/latex]$
$[latex]d=\frac{\ln\left(\frac{1}{n}\right)}{\ln\left(\frac{3}{4}\right)}[/latex]$
$[latex]d=\frac{\ln\left(n\right)}{\ln\left(\frac{4}{3}\right)}[/latex]$
tatsächlich wird die Zahl der Durchläufe darunter liegen (weil div den Kommateil ignoriert). Das ist eine Obergrenze.

Geschrieben von ubik am 12.04.2015 um 17:31:

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.