Rekursionsgleichung bestimmen

[yeha]

Hallo,

ich finde im Internet leider keine richtige Anleitung dazu wie ich die Laufzeit zu einem rekursiven Algorithmus bestimmen kann, deshalb wende ich mich an euch, in der Hoffnung, dass ihr mir helfen könnt 😀
Klar ist, dass man die Rekursionsgleichung dazu braucht, aber ich versteh nicht so richtig wie ich diesen aufstellen muss.
a*t(n/b)+f(n)
In Vorlesungsfolien habe ich gelesen, dass a die Anzahl der Unterprobleme und b die Größe der Unterprobleme sein soll, das hilft mir aber null weiter. Wie bestimme ich denn die Größe eines Unterproblems?

Vielleicht kann mir das ja jemand anhand des Fibonacci-Algorithmus erklären?

 int fib(int n)
    {
    if (n <= 2) return 1
    else return fib(n-1) + fib(n-2)
    }

 

[yeha]

Also wenn ich es richtig verstanden habe, ist a gleich 1, da es nur einen rekursiven Aufruf gibt, b müsste gleich 2 sein? und f(n)?

 

[yeha]

okay f(n) müsste 1 sein. damit hätte ich T(n/2)+1 und laut mastertherorem wäre die Laufzeit dann O(n^log2(1)) und das wäre doch n^0 also O(1) xD

 

[Nuiton]

Das Mastertheorem kannst du fuer dieses Beispiel nicht benutzen, da die Gleichung in der Form von
T(n) = aT(n/b) + f(n) sein muss.

1. if (n <= 2) return 1
2. else return fib(n-1) + fib(n-2)

T(n) = O(1) + T(n-1) + T(n-2)
oder
T(n) = T(n-1) + T(n-2) + O(1)

Wir nehmen an das T(n-1) = O(2^(n-1)). Es folgt T(n) = O(2^(n-1)) + O(2^(n-2)) + O(1) = O(2^n).