Rekursive Zeit Gleichungen?
Wie löst man diese Zeit Gleichung
T(n)=T(n-2)+log n
![](https://images.gutefrage.net/media/default/user/9_nmmslarge.png?v=1551279448000)
sicher, dass zwischen n und 2 ein Minus und kein Geteilt steht?
![](https://images.gutefrage.net/media/default/user/11_nmmslarge.png?v=1551279448000)
Ja ziemlich sicher
1 Antwort
![](https://images.gutefrage.net/media/default/user/9_nmmslarge.png?v=1551279448000)
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