[DSAL] Höhe eines Rekursionsbaums

[Progra] Programmierung
[DSAL] Datenstrukturen und Algorithmen
[SWT] Softwaretechnik
[DB] Datenbanken und Informationssysteme

Höhe eines Rekursionsbaums

Beitragvon paco89 » 19.08.12 18:35

hallo,

ich habe da ne frage zu der Höhe bei Rekursionsbäumen. und zwar wenn z.B. das "n" auf jeder ebene immer durch 4 geteilt wird, dann ist das ja log_4(n).
auf den vorlesungs-folien steht auch z.B, log_4(n) . aber bei den musterlösungen zu den Übungsblättern steht manchmal log_4(n) - 1 oder log_4(n) +1.

woran erkenn ich denn wann ich +1 und wann ich -1 schreiben muss?

denn davon hängt auch letztendlich die lösung ab. je nachdem wofür man sich entscheidet, kommt man auf unterschiedliche endlösungen, deswegen bin ich ein wenig verwirrt....kann mir da jmd. weiterhelfen?
paco89
 
Beiträge: 115
Registriert: 05.12.10 05:04

Re: Höhe eines Rekursionsbaums

Beitragvon dtt » 26.08.12 10:36

Naja, asymptotisch betrachtet ist das egal. Deswegen kann man dasn Plusminus 1 weglassen.
Sollte man z.B. T(0) als Basisfall haben, dann muss man zusätzlich eins auf die Höhe des Baums dazuaddieren.
dtt
 
Beiträge: 5
Registriert: 17.10.11 14:04
Studiengang: Informatik (B.Sc.)
Studiert seit: WS 11/12


Zurück zu Praktische Informatik