O-Schreibweise < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:56 Di 10.06.2008 | | Autor: | Dnake |
| Aufgabe | Ermitteln Sie möglichst gute (enge) Komplexitätsmaße in O-Schreibweise für die folgenden rekursiv definierten Funktionen T(n), die natürliche Zahlen >0 auf natürliche Zahlen abbilden:
a) T(1) = 1
T(n) = T(n-1)+n für n > 1
b) T(1) = 1
T(n) = 2*T(n-1) für n > 1 |
Hallo,
weiss nicht wie ich an so eine Aufgabe rangehen soll, muss ich da sowas wie eine Reihe entwickeln und die dann in O-Schreibweise überführen.
Ich habe im Netz ja einiges über O-Schreibweise gefunden und auch soweit nachvollziehen können, aber in Zusammenhang mit rekursiv definierten Funktionen habe ich nichts gefunden.
Bin für jeden Tip dankbar!
Gruß
Jan
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:28 Di 10.06.2008 | | Autor: | statler |
Hi Jan!
> Ermitteln Sie möglichst gute (enge) Komplexitätsmaße in
> O-Schreibweise für die folgenden rekursiv definierten
> Funktionen T(n), die natürliche Zahlen >0 auf natürliche
> Zahlen abbilden:
>
> a) T(1) = 1
> T(n) = T(n-1)+n für n > 1
>
> b) T(1) = 1
> T(n) = 2*T(n-1) für n > 1
> weiss nicht wie ich an so eine Aufgabe rangehen soll, muss
> ich da sowas wie eine Reihe entwickeln und die dann in
> O-Schreibweise überführen.
>
> Ich habe im Netz ja einiges über O-Schreibweise gefunden
> und auch soweit nachvollziehen können, aber in Zusammenhang
> mit rekursiv definierten Funktionen habe ich nichts
> gefunden.
Deswegen wär mein Ratschlag, daß du dir zunächst überlegst, ob es eine explizite Formel für diese beiden Funktionen gibt. Wenn dir sonst nichts einfällt, könntest du z. B. die ersten paar Werte ausrechnen und dann eine Formel raten (und sie dann vielleicht sogar noch beweisen).
Gruß aus HH-Harburg
Dieter
|
|
|
|
