Rekursive Zeit Gleichungen?
Wie löst man diese Zeit Gleichung
T(n)=T(n-2)+log n
sicher, dass zwischen n und 2 ein Minus und kein Geteilt steht?
Ja ziemlich sicher
1 Antwort
Ok, mit einem Geteilt hätte ich dich einfach auf das Master Theorem verwiesen.
Das Funktioniert nur für ungerade n:
Bei jedem rekursiven Aufruf, wird das Problem um 2 kleiner. Also gibt es (n-1)/2 aufrufe. Also kommt zum Basisfall T(1) noch (n-1)/2 Mal der Aufwand log n dazu.
Also:
Woher ich das weiß:Studium / Ausbildung – Informatikstudium