PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Rekurrenz interpretieren



Doppelhelix
13.10.2005, 13:08
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

zefram
15.10.2005, 01:03
Vielleicht kannst du die komplette Aufgabenstellung im Originallaut posten?

15.10.2005, 11:22
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)

Doppelhelix
16.10.2005, 11:20
Sorry, war leider nicht angemeldet.

hl_angel
17.10.2005, 16:56
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)?