 asymptotische Verhalten beweisen |
Hang-over
unregistriert
 |
|
| 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:24 |
|
|
|
|
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 ![[latex]t_n = \sum_{i=1}^n2\cdot i - 1= n\cdot(n+1)-1[/latex]](http://www.matheboard.de/latex2png/latex2png.php?t_n = \sum_{i=1}^n2\cdot i - 1= n\cdot(n+1)-1) .
Lässt sich mit Induktion auch beweisen.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
01.05.2016 10:57 |
|
|
Hang-over
unregistriert
|
|
Deine Summe ist falsch in der Aufgabe T(n) = 2* (Summe von i=1 bis n) i
|
|
|
01.05.2016 11:25 |
|
|
Hang-over
unregistriert
|
|
Also muss man das einfach nur mit induktion
Aber im Internet hab ich immer Beweise gefunden mit o Notation so muss das doch gehen ??
|
|
|
01.05.2016 11:26 |
|
|
Hang-over
unregistriert
|
|
vred.bioinf.uni-sb.de/prog2_ss04/lectures/rekursion.pdf
|
|
|
01.05.2016 11:37 |
|
|
|
|
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.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
01.05.2016 19:47 |
|
|
|
|
|
