Laufzeit Rekursion

11.02.2008, 15:04

JROppenheimer

Laufzeit Rekursion

Sorry, wenn ich euch mit so Banalitäten nerven muss, aber ich hab nicht die geringste Ahnung, wie ich von einer Rekursion RICHTIG die Laufzeit bestimme ...
Die Funktion, die ich habe sieht so aus:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

int berechne(i,j)
{
    int laenge;
    int summe;
    laenge = j-i+1;
    if(laenge <= 1)
        return 1;
    summe = berechne(i, i + laenge/3-1) + berechne(i + 2*laenge/3 +1, j)
    for (int k = i; k <= j; k++)
        summe += 1;
    return summe;
}

Es geht um die Laufzeit des Aufrufs berechne(1,n) wobei n eine Potenz von 3 ist.

Also die for-Schleife läuft O(n).
Bin nicht sicher wie ich das mit den Rekursionen mache.
Also wenn n=1 ist, dann bricht der ja ab, dann ist T = O(n)

Und wenn n nicht 1 ist, dann teilt der das ja auf in 2 weiter Funktionen: Vlt sowas wie:
T(n) = 2*O(n/3) + O(n) ????

edit*: wird das vlt T(n) = O(log3 n)

??

13.02.2008, 17:39

Auf diesen Beitrag antworten »

Tobias

Also Rumgerate wird dich hier nicht weiterbringen. Erstmal musst du klar aufstellen, wieviele Rechenschritte in einem Durchgang gemacht werden. Da die Prozedur rekursiv ist, kannst du also für die Anzahl Rechenschritte auch eine rekursive Angabe machen:

Sei $[latex]\tau(1, n)[/latex]$ die Anzahl Rechenschritte, die [latex]T(1, n)[/latex]

benötigt. Wir stellen fest, dass jede Menge Operationen in O(1) absorbiert werden können. Ins Blickfeld unserers Interesses rückt also nur noch die for-Schleife und die rekursiven Aufrufe:

$[latex]\tau(1, n) = \tau(1, \frac{n}{3}) + \tau(1+\frac{2n}{3}+1, n) + n + O(1) [/latex]$

Es werden also alle Elemente der Folge aufaddiert und im rekursiven Abstieg jeweils das vordere und das hintere Drittel des Arrays bearbeitet. Abgebrochen wird nach einer bestimmten Rekursionstiefe, die wir mal c nennen (ich vermute $[latex]c = \lfloor \log_3(n) \rfloor[/latex]$ oder irgendwas in der Nähe).

Stellen wir eine Summenformel auf, die aussagt, dass in der ersten Rekursionstiefe n Elemente aufaddiert werden, in der zweiten Rekursionstiefe dann nur noch 2/3*n, danach 4/9*n, etc:

$[latex]\tau(1, n) = n\sum_{i=0}^{c}\frac{2^i}{3^i} + O(1) [/latex]$

Die Summe können wir nach oben gegen eine geometrische Reihe abschätzen (weswegen wir das c auch nicht genau benennen müssen):

$[latex]\tau(1, n) = n\sum_{i=0}^{c}\frac{2^i}{3^i} + O(1) \leq n \sum_{i=0}^{\infty}\left(\frac{2}{3}\right)^i + O(1) = 3n + O(1) = O(n)[/latex]$

Edit:
Da in jedem Durchgang die Summe um 1 erhöht wird, ist das Ergebnis der Prozedur tatsächlich auch ein Indiz für die Laufzeit. Man kann also sogar praktisch verifizieren, dass das Ergebnis von T(1, n) für große n immer näher an 3n heranreicht.

Neue Frage »

Antworten »

Laufzeit Rekursion

Verwandte Themen