Gleichung einer Laufzeit

[valenterry]

Hallo!

Ich möchte die Laufzeitkomplexität oder Laufzeit eines Algorithmus t(n) bestimmen. Und zwar sieht er wie folgt aus: t(n) = a * t( b^(1/k) ) + log_2(n)

Ich denke die Laufzeit bestimmt sich durch folgende Gleichung:

Summe[von i=0 bis slog_k(n)]: a^i * log_2( n^(1/(k^i)) )

das kann man - denke ich - vereinfachen zu:

log_2(n) * Summe[von i=0 bis slog_k(n)]: (a/k)^i

slog_k(n) ist übrigens der superlogarithmus. So wie ^ (sprich: hoch) eine mehrmaliges Ausführen von Multikplikationen ist, ist der superlogarithmus ein mehrmaliges Ausführen vom (einfachen) Logarithmieren.

Naja, auf jedenfall ist die Laufzeit in O(log_2(n)), falls k>a. Denn dann spielt der Summenterm keine große Rolle, weil dort ein Bruch drinsteht, der immer kleiner wird. Wenn hingegen a=k, dann ist die Laufzeit in O(log_2(n) * slog_k(n)), weil ja die Summe ja slog_k(n) mal oft 1 + 1 + 1 + ... + 1 gerechnet wird.
Aber was passiert, wenn a>k ist? Da häng ich momentan. Ich hoffe, dass soweit alles richtig ist.
Kann mir da jemand vielleicht weiterhelfen? Ihr könnt gerne auch Gedanken posten, die mir vielleicht einen Ansatz ermöglichen, auch wenn ihr die Lösung nicht kennt.

Viele Grüße.

[Gunnar Bittersmann]

@@valenterry:

nuqneH

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]

Hm, auf der rechten Seite steht auch wieder [latex]t(b^{\frac 1k})[/latex]. Ich würd sagen, der Algorithmus hat eine seeeeeeehr laaaaaaange Laufzeit.

Qapla'

[Bademeister]

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