Rekursive Zeit Gleichungen?

TheOrzoBiased  17.11.2020, 19:14

sicher, dass zwischen n und 2 ein Minus und kein Geteilt steht?

Benitutu 
Fragesteller
 17.11.2020, 19:23

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