nicht angemeldet
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