Rekurrenz (Rekursion)
-
Hallo zusammen.
Ich muß für meine Informatik Übung eine Aufgabe zum Thema Rekurrenz bzw. Rekursion lösen. Ich habe aber erhlich gesagt davon keine Ahnung.
Hier die Aufgabenstellung:Bestimmen und beweisen Sie eine möglichst gute oberer Schranke in O-Notation für das asymptotische Verhalten der folgenden Rekursion:
T(1)=1
T(n)=T(n-1) + n für n>= 2Wäre super wenn ihr mir weiterhelfen könntet.
MFG
Simon
-
Lieber Simon, vielleicht würde es dir erstmal helfen zu versuchen, T(n) auch direkt (also nicht rekursiv) darzustellen.
-
Als kleiner Tipp:
einfach mal T(1), T(2), T(3) ausrechnen. Dann die Zahlen anschauen und versuchen ein Schema zu finden. Das kann man dann anschließend mit Induktion beweisen und danach noch das O-Kalkül... fertig.
Alternativ könnte man sich auch mal anschaun, wie
T(n)-T(n-1) aussieht. Das dann verlängern auf T(n)-T(n-2) und so weiter bis zu T(n)-T(1) dann noch T(1) wieder aufaddieren und das Ergebnis steht da. Ist im Prinzip aber nicht anderes.
MfG Jester
-
Btw: Nettes crossposting... http://www.studenten-city.de/forum/showthread.php?t=25312