Laufzeit einer Funktion, Landau Symbole |
04.11.2012, 16:30 | Konstantin | Auf diesen Beitrag antworten » |
Laufzeit einer Funktion, Landau Symbole 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. |
||
04.11.2012, 23:25 | 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 |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |