buzz_lightzyear

Hallo, ich hab hier folgendes Beispiel vor mir: T(n)= T(n-a)+n, T(n)=O(1) für n <= 1. Durch iteratives Einsetzen erhält man lt. Beispiel folgende Gleichungen: T(n)= T(n-2a)+2n, T(n)= T(n-4a)+4n, T(n)= T(n-8a)+8n, ... Ich setze also für die erste Gleichung für n (n-a) ein... soweit klar, auch bei den nächsten Schritten... aber wie zum Teufel bzw. warum hab ich dann 2n, bzw 4n usw. da stehen. Klar, 4 ist das doppelte von 2, 8 von 4 usw... aber warum nicht irgendeine andere Zahl... Sorry aber ich komm da echt nicht drauf... ;-( Danke für eure Hilfe! :-) lg buzzzzzz

Hallo nochmal, ich hab gleich noch eine Frage zu einem anderen Beispiel und zwar gehts hier um die Fibonacci-Folge (rekursiv). Die Rekursionsgleichung dazu lautet: T(n)=O(1) + T(n - 1) + T(n - 2)= //Rekursionsgleichung, alles klar =O(1) + O(1) + T(n - 2) + T(n - 3) + T(n - 2) Hier hab ich ein kleines Verständnisproblem und zwar: Ich bin hier einen Rekursionsschritt tiefer, sprich ich habe (n-1) für n in die erste Gleichung eingesetzt -> ok! Aber woher kommt das letzte T(n - 2)? Das kann ich nicht nachvollziehen... :-( Jemand einen Tipp für mich? :-) Thx & Lg buzz

Hallo, danke für deine Antwort, ja es ist O(n). Trotzdem weiß ich eben nicht, wo das T(1) = T(n-k) herkommt... Unser Prof. nimmt das eben immer als so einfach an, dass sowas nicht erwähnt werden muss. -.- Thx & Lg

Hallo, ich habe folgendes Beispiel vor mir liegen; es geht um die rekursive Berechnung der Fakultät: FAKULTAET_REKURSIV(n) 1: IF n= 1 THEN 2: RETURN 1 3: ELSE 4: RETURN(n*FAKULTAET_REKURSIV(n-1)) Soweit alles klar :-) Dann gehts zur Rekursionsgleichung: T(n) = O(1) + T(n-1) O(1): konstante Zeit, die die Zeilen 1-3 benötigen T(n-1): Laufzeit um eins verringert, da die Funktion ja mit (n-1) aufgerufen wird -> auch noch klar :-) Dann wird die Rekursionsgleichung gelöst und eine allgemeine Formel hergeleitet: k*O(1) + T(n-k) -> ja, das ist auch noch klar! :-) Aber jetzt kommt das Problem: Man will eine Lösung unabhängig von k. In dem Beispiel vor mir hab ich nun: "Mit T(1) = T(n-k) bekommt man n-k = 1 => k = n - 1 und setzt das in die obige allgemeine Formel ein." Warum setzt man hier T(1) = T(n-k)?? das ist ja mMn nicht das Gleiche?!? Kann mir vllt jemand erklären warum das so ist? Thx & Lg buzzzzzz