Druckbare Version
Hey Leute,
ich habe hier die Rekurrenz eines Algorithmus und soll diese nun interpretieren, und zwar um welche Art von Algorithmus es sich dabei handelt.
T(n) = T(n/3) + 5 für n >= 2
Vielleicht weis jemand eine Antwort darauf und kann mir helfen.
Schon im voraus Danke
Vielleicht kannst du die komplette Aufgabenstellung im Originallaut posten?
Okay, hier kommt die ganze Aufgabenstellung, a.) und c.) hab ich schon gelöst.
Rekurrenzen
1. Entfaltung + Beweisen
a) Lösen Sie folgende Rekurrenz mittels Entfaltung:
T(1) = 5
T(n) = T(n/3) + 5 für n ≥ 2
b) Um welche Art von Algorithmus handelt es sich hier? Interpretieren Sie
die Rekurrenz.
c) Beweisen Sie (mittels Raten und Beweisen), dass Ihr Ergebnis aus 1.a)
richtig ist.
Antwort a.) und b.): O(T(n)) = log(n)
Sorry, war leider nicht angemeldet.
Google mal unter "Erzeugende Funktionen", damit hat mich der Prof. Baron auf der TU Wien damals gequält. Der Kerl hat auch nette Bücher geschrieben.. nachlesen kann nicht schaden ... was ich mich nur frage: was ist T(n/3)? ist T(2/3) denn definiert? ist das T(1) oder T(0)?