Laufzeit einer Funktion, Landau Symbole

Neue Frage »

Konstantin Auf diesen Beitrag antworten »
Laufzeit einer Funktion, Landau Symbole
Meine Frage:
Es seien a, b, c, d Elemente R Konstanten mit c, d >=0 und 2=<b<a. Außerdem sei T : N nach R>=0
eine monoton steigende Funktion, welche die folgenden Bedingungen erfullt:
 T(n)=< d für n=<b und
 T(n)=< c*n + a*T([n/b](nach oben gerundet)) für n>b.
Zeigen Sie, dass dann T(n) = O(n^logb(a)) gilt.

Meine Ideen:
Ich habe generell Verständnisprobleme mit Funktion-Laufzeit Aufgaben. Hier z.B. ist mir klar, dass die T(n) auf zwei Intervalen =<b und >=b unterschiedlich definiert wird. Und dann muss man diese Funktion mit einer Logarithmus-Funktion vergleichen indem man Konstante vernachlässigen kann. Aber wie man hier genau verfahren muss weiß ich nicht. Brauche von euch keinerlei Lösung oder so, sondern ein Tipp wie man mit Aufgaben solcher Art überhaupt vorgeht.
Abakus Auf diesen Beitrag antworten »
RE: Laufzeit einer Funktion, Landau Symbole
Hallo,

das T ist ja via einer Rekursion definiert: die erste Ungleichung ist der einfache Fall, die zweite führt ein großes Argument von T auf ein kleineres zurück.

Oder anders: du programmierst eine Rekursion, in der das Problem um den Faktor b kleiner wird, du aber a mal rekursiv aufrufen musst. Es ist nicht ganz unwichtig, diese Formel genau zu kennen!

Überlege einfach, wie oft du n durch b teilen kannst, bis du in den ersten Fall kommst: sooft läuft die Rekursion rückwärts. Kannst du die Rekursion in sich einsetzen und schauen wohin du damit kommst?

Abakus smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »