nicht angemeldet
Hi Gunnar und valenterry.
t(n) = a * t( b^(1/k) ) + log_2(n)
?? a, b und k sind Konstanten?
Zur Berechnung von [latex]t(n)[/latex] muss [latex]t(b^{\frac 1k})[/latex] berechnet werden: [latex]t(b^{\frac 1k}) = a \cdot t(b^{\frac 1k}) + \log_2 b^{\frac 1k}[/latex]
Ich würd sagen, der Algorithmus hat eine seeeeeeehr laaaaaaange Laufzeit.
?? Es steht doch ueberhaupt kein Algorithmus da.
Wenn a, b und k Konstanten sind, ist auch [latex]a \cdot t(b^{\frac 1k}) =: c[/latex] konstant, so dass der (beste) Algorithmus zum Berechnen von [latex]t(n) = c + \log_2 n[/latex][1] gerade die Komplexitaet des Logarithmus hat.
Und wenn man den Algorithmus implementieren will, dann kann man c[1] auch ausrechnen. [latex] n = b^{\frac 1k} [/latex] gesetzt liefert
[latex] c=- \frac{a}{a-1} \log_2 b^{\frac 1k} [/latex]
(wenns denn stimmt..)
Von Deinen, valenterry, Komplexitaetsausfuehrungen hab ich leider kein Wort verstanden. Woher kommen die denn?
[1] mit gewuenschter Genauigkeit
Viele Gruesse,
der Bademeister
Gunnar Bittersmann