Laufzeit, asymptotische Schranken |
| 16.01.2017, 17:36 | whatismath_02 | Auf diesen Beitrag antworten » | ||||
| Laufzeit, asymptotische Schranken Gegeben sei die rekursive Funktion T (n) = 2T (n ? 1) + 1 mit T (1) = 1. Zeigen Sie, dass T(n) = O(2^n) für n ? ?. Meine Ideen: Ich weiß, dass T(n) = O(2n) für n ? ? heißt, dass T(n) langsamer oder gleich schnell wie 2^n wächst. Ich würde normalerweise das Verhältnis der Grenzwerte von T(n) und 2^n berechnen (lim n-> unendlich von T(n)/2^n = K) und daraus leiten, dass 0<=K<unendlich ist und die in der Aufgabenstellung stehende Gleichung somit bewiesen wird. Es ist nur etwas kompliziert, da T(n) = 2T(n-1) +1 ist. Und wofür ist denn T(1) = 1? Kann es mir jemand bitte erklären? Danke! |
||||||
| 16.01.2017, 17:45 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
| (wieder mal) Copy+Paste-Gewurstel Das ganze bitte nochmal, diesmal mit verständlichen Symbolen an den Stellen der vielen "?" . 
|
||||||
| 16.01.2017, 17:50 | whatismath_03 | Auf diesen Beitrag antworten » | ||||
| RE: Laufzeit, asymptotische Schranken Edit: Meine Frage: Gegeben sei die rekursive Funktion T (n) = 2T (n - 1) + 1 mit T (1) = 1. Zeigen Sie, dass T(n) = O(2^n) für n -> unendlich. Meine Ideen: Ich weiß, dass T(n) = O(2n) für n -> unendlich heißt, dass T(n) langsamer oder gleich schnell wie 2^n wächst. Ich würde normalerweise das Verhältnis der Grenzwerte von T(n) und 2^n berechnen (lim n-> unendlich von T(n)/2^n = K) und daraus leiten, dass 0<=K<unendlich ist und die in der Aufgabenstellung stehende Gleichung somit bewiesen wird. Es ist nur etwas kompliziert, da T(n) = 2T(n-1) +1 ist. Und wofür ist denn T(1) = 1? Kann es mir jemand bitte erklären? Danke! |
||||||
| 16.01.2017, 21:02 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
RE: Laufzeit, asymptotische Schranken
Aus beidem lässt sich per Vollständiger Induktion sofort für alle nachweisen. Das nachzuweisende ist dann ja nur eine kleine Folgerung.
Seltsame Frage: Die Rekursion darf doch nicht in der Luft hängen, sondern muss einen Startwert haben. |
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
