infostudium.de

von **LonliLokli** » 03.08.08 22:32

Wie bestimmt man O(...) mit Master-Theorem von der folgenden Funktion
$T(n)=T(sqrt(n))+1$ .
Was mir einfällt, ist
$m=sqrt(n) \\ T(m^2)=T(m)+1$

Aber das bringt mich nicht weiter...

von **NeX** » 04.08.08 09:29

mal mit dem direkten Ansatz versucht?

Erst ist es $T(n^{\frac{1}{2}})$ dann ist es $T(n^{\frac{1}{4}})$ ..... vielleicht bringt dich das deiner Lösung näher....

also das Master-Theorem würde ich aussen vor lassen

von **LonliLokli** » 04.08.08 10:48

NeX hat geschrieben:mal mit dem direkten Ansatz versucht?

Erst ist es $T(n^{\frac{1}{2}})$ dann ist es $T(n^{\frac{1}{4}})$ ..... vielleicht bringt dich das deiner Lösung näher....

also das Master-Theorem würde ich aussen vor lassen

Bei der Aufgabenstellung steht, dass man diese Rekursion mit dem MT lösen soll.

von **LonliLokli** » 04.08.08 11:25

Ich habe die lösung zu der Afgabe gefunden, da wird tatsäslich mit dem direktem einsatz die aufgabe gelöst.
$O(n)\in\theta(lglg(n))$

von **YtKM** » 04.08.08 16:09

Hallo,
könntest du uns vielleicht auch noch die komplette Aufgabenstellung oder den Lösungsweg per direktem Ansatz mitteilen?

Vielen Dank
ytkm

von **LonliLokli** » 04.08.08 17:08

Aufgabenstellung:
Übungsblatt 4, 1.Aufgabe Sommersemester 2005 von Prof. Kobbelt erhältlich unter
http://www-users.rwth-aachen.de/martin.weusten/index.php?id=uni_info
Lösung
http://s-inf.de/Skripte/DaStru.1998-SS-Ney.(EB).TestKlausurUndLoesung.pdf

von **YtKM** » 04.08.08 17:23

ok, danke. Mit dem Zusatz T(2)=1 ist die Aufgabe gut lösbar. :-)

von **LonliLokli** » 04.08.08 17:46

YtKM hat geschrieben:ok, danke. Mit dem Zusatz T(2)=1 ist die Aufgabe gut lösbar.

Bei MT-Aufgaben wird so was immer vorausgesetzt, sonst kannst du MT ger nicht anwenden...

Mich interessiert, ob man die Aufgabe mit MT lösen kann, denn wenn in der Klausur steht, dass man die mit MT machen muss, muss man auch damit die machen...

von **YtKM** » 04.08.08 17:51

Ich versuchte es zuerst mit T(1)=...
Das bringt nur bei dieser Aufgabe leider nichts, deswegen ging es nur mit T(c) mit c>1.

Einen gültigen Ansatz mit Mastertheorem kenne ich nicht, da wird nur T(n)=T(b^-1*n) hatten. Beliebige Funktionen haben wir nicht auf n angewendet, sondern lediglich lineare Funktionen durch Substitution gelöst..

infostudium.de

Forum zum Informatikstudium an der RWTH Aachen

[DSAL] Asymptotische Verhalten folgender Funktion

Asymptotische Verhalten folgender Funktion