0 Daumen
282 Aufrufe

Aufgabe:

Wenn man einen einfachen Fibonacci Algorithmus hat mit:

$$F_0 = 0\\ F_1 = 1\\ F_n = F_{n-1} + F_{n-2} \quad \text{for } n \geq 2$$

Wie beweißt man folgende Obergrenze für die Zeikomplexität ?

$$T(n) \leq 2^n \text{ für alle}   n \geq 0$$

Problem/Ansatz:

$$\text{Anfang:  } T(0) =  1 \text{und } 2^0 = 1 $$

Dann:

$$\text{[1]    } T(n) = 2^{n-1}+2^{n-2}+1 \leq 2^n$$

Und soweit ich weiß, sollte das der nächste Schritt sein.
$$\text{[2]    } 2^{n-1}+1 \leq 2^{n-1} \quad \text{      dasteht. }$$

Ich kann diesen Schritt nicht nachvollziehen. Hab alle Potenzgesetze die ich kenne rausgekramt, aber komme einfach nicht  von [1] nach [2]. Und verstehe auch nicht wie mir der Anfang weiterhelfen könnte.

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

Hallo
dein 2. ist einfach falsch! a+1<a ist immer falsch. aber voeööeocj hast du dich vertippt?

2n−2+1≤2 n−1

2^n=2n-1+2n-1=2n-1+2n-2+2n-2 >2n-1+2n-2+1; für n>2

Gruß lul

Avatar von 108 k 🚀

Vielen Dank, ja du hast recht. da sollte 2^{n-2} +  1 auf der linken Seite stehen.
kannst du mir sagen, warum man das hier machen darf ?
2^{n}=2^{n-1}+2^{n-1}

2^n=2*2n-1=(1+1)2n-1

Gruß lul

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
+1 Daumen
1 Antwort
Gefragt 30 Mär 2017 von Gast

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community