Rekurrenzgleichung lösen < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:56 Mo 31.01.2011 | | Autor: | anno |
| Aufgabe | Lösen Sie die Rekurrenzgleichung, indem Sie sie mehrfach auf sich selbst anwenden. Geben Sie das Ergebnis möglichst genau im O-Kalkül an.
Hinweis: Es gilt 2^(k−1) + 2^(k−2) + . . . + 1 = [mm] 2^{k} [/mm] - 1 |
Hallo,
ich soll hier eine Rekurrenzgleichung lösen. Also meine erste Vermutung ist, dass ein O-Kalkül O(n) gilt. Aber mir fällt gerade nicht ein wie ich das als Rekurrenzgleichung schreiben soll.
hat da jemand eine Idee?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:37 Mo 31.01.2011 | | Autor: | felixf |
Moin!
> Lösen Sie die Rekurrenzgleichung, indem Sie sie mehrfach
> auf sich selbst anwenden. Geben Sie das Ergebnis möglichst
> genau im O-Kalkül an.
> Hinweis: Es gilt 2^(k−1) + 2^(k−2) + . . . + 1 = [mm]2^{k}[/mm]
> - 1
> Hallo,
>
> ich soll hier eine Rekurrenzgleichung lösen. Also meine
> erste Vermutung ist, dass ein O-Kalkül O(n) gilt. Aber mir
> fällt gerade nicht ein wie ich das als Rekurrenzgleichung
> schreiben soll.
$O(n)$ liegt etwa vor, wenn du eine Rekurrenzgleichung der Form [mm] $x_{n+1} [/mm] = [mm] x_n [/mm] + [mm] \alpha$ [/mm] hast mit einer Konstanten [mm] $\alpha$.
[/mm]
Ich vermute, hier geht es eher um etwas exponentielles. Da du die Gleichung selber nicht nennst kann man jedoch nur im Nebel herumstochern...
LG Felix
|
|
|
|
