asymptotische Verhalten beweisen |
| 01.05.2016, 10:24 | Auf diesen Beitrag antworten » |
| Hang-over | asymptotische Verhalten beweisen Meine Frage: Rekursiongleichung beweisen T(1) =1 T(n)=T(n-1)+2n, n=>2 Hinweis T(n)=2*(n(n+1)/2) Meine Ideen: Ich weiß nicht wie ich hier vorgehen soll, hab schon einige Beweise mir angeguckt wie die da vorgehen, aber da wird immer zuerst eine Obere Schranke vermutetet Und dann die Vermutung in T(n)<= c * (Vermutung) eingesetzt aber wie kommt man denn drauf Wäre super wenn mir hier jemand erklären könnte wie das funktioniert |
|
|
|
| 01.05.2016, 10:57 | Auf diesen Beitrag antworten » |
| eulerscheZahl | t(1) = 1 t(2) = 4+t(1) = 4+1 = 5 t(3) = 6+t(2) = 6+4+1 = 11 t(4) = 8+t(3) = 8+6+4+1 = 19 Hier werden (bis auf die letzte Zahl) immer geradzahlige Zahlen addiert. Es sieht aus, als wäre Lässt sich mit Induktion auch beweisen. |
| 01.05.2016, 11:25 | Auf diesen Beitrag antworten » |
| Hang-over | Deine Summe ist falsch in der Aufgabe T(n) = 2* (Summe von i=1 bis n) i |
| 01.05.2016, 11:26 | Auf diesen Beitrag antworten » |
| Hang-over | Also muss man das einfach nur mit induktion Aber im Internet hab ich immer Beweise gefunden mit o Notation so muss das doch gehen ?? |
| Anzeige | |
|
|
|
| 01.05.2016, 11:37 | Auf diesen Beitrag antworten » |
| Hang-over | vred.bioinf.uni-sb.de/prog2_ss04/lectures/rekursion.pdf |
| 01.05.2016, 19:47 | Auf diesen Beitrag antworten » |
| eulerscheZahl | Du hast in der Lösung auch eine andere Formel als ich (beachte die -1). Die exakte Formel kann man mit Induktion zeigen. Für die nicht exakte geht das natürlich nicht. |
|
|