Notation Bsp. aus altem Test.

[Vallian]

Das Beispiel ist glaube ich aus der Prüfung vom 14 März 2003 | f(round(n/3)) + f(n - round(n/3)) n>7
f(n)=| n+1 n< 6 gerade| n+2 n< 7 ungerade
okay,klar ist das die oberste Zeile die wichtigste ist. Man kann sich die Rekursiven aufrufe als Baum vorstellen.

zb. n=21

f(21)
f(7) + f(14)
f(2)+f(5) f(5) + f(9)
(2+1)+(5+2)+ f(3) + f(6)
(2+1)+(5+2)+(5+2)+(3+2)+(6+2)


In der letzten Zeile steht unsere Laufzeo oder ?
Das errinnert an einen Binärenbaum, ich dacht ers an 2^n doch dafür
musst der baum größer sein.
Naja vielleicht kann mir dass ja jemand verständlich machen.

[Vallian]

So wie es aussieht ist die Lauf zeit teta(n). Habs ausprobiert ;-).
Ausserdem glaube ich dass mal gehört zu haben.

Heißst dass dass man im Grunde ( log n ) + ( n - Log n ) = n hat ?
Das wäre dann ja richtig einfach

[llbyz]

ähämm, also iss es nicht so daß

f(round(n/3)+f(n-round(n/3)) also für zB. n=9
f(3)+f(9-3) =9
... immer gleich bleibt????

[JGoblin]

Prinzipiell hab ich IMMER ein problem beim auflösen von rekursionen
wie geh ich an eine rekursiv definierte Laufzeitfunktion heran??
z,b.:
f(n) = f(n/2) + n für n >= 2 und 0 andernfalls
wie geh ich an so ein bsp heran ??