Laufzeitanalyse von rekursiven Codes

int berechne1(int n)
{
    int sum = 0;


    for(int i = 0; i < n/2 ; i++)  { // es wird n/2 mal eine konstante operation ausgeführt => c1* n/2 
        sum += 2*i-1;
    }

    if (n<=0) // die ganze funktion wird solange rekursiv ausgeführt bis die Abbruchbedingung erfüllt ist, => T(n-1)
         return sum; // auch wenn das nur einmal gemacht wird, kostet es eventuell zeit => c2
    else
        sum+4*berechne1(n-1);
}

Die Theorie dahinter ist das Master-Theorem - aber dazu gibt es sicher in Vorlesungsfolien/Skriptum/OdervonwoauchimmerdumitdemProblemkonfrontiertwarst mehr (eventuell hilft ja auch googlen). :verycool:

Hallo,

Zitat von CwieZebra

[CODE]Die Theorie dahinter ist das Master-Theorem - ...

ich habe mir die drei Fälle angeschaut, aber ich weiß nicht, wann welcher Fall anzuwenden ist :confused:

Kann mir bitte jemand sagen, wie ich den richtigen Fall bestimmen kann?

Im Anhang habe ich ein Beispiel, was ich nicht richtig lösen kann.

Danke vorab
Viele Grüße
Asg

informatik-forum.net/attachment/23021/

PS: Wie kann ich hier im Forum Sonderzeichen wie die Oh-Notationen schreiben? Oder ist es nicht möglich?

ich glaub, ich muss alle drei Fälle testen, um herauszufinden, welcher Fall zutrifft, oder???

Ich habe noch etwas weiter recherchiert und habe folgende Beispiele gefunden:
Master Theorem - Computer Science & Engineering

Die Bedingungsprüfung in diesem Skript finde ich einfacher. Wobei ist mir nicht ganz klar, was man als d nehmen soll, wenn eine Funktion f(n) mehrere Exponenten hat z. B. f(n) = n² + n log n. Wahrscheinlich muss der größte Exponent für d gewählt werden, in diesem Fall d = 2, oder??

Hier wird aber auf der Seite 4 geschrieben, dass Master-Theorem auf nicht polynomiale f(n) wie 2ⁿ nicht anwendbar ist ....

Master Theorem: Practice Problems and Solutions
... aber hier wird das Master-Theorem auf eine solche f(n) im Beispiel 3 angewendet.

Wo ist denn mein Denkfehler?

Viele Grüße
Asg

Hallo,

danke für den Tipp für den Editor.

Viele Grüße
Asg