![[HaBo]](/styles/default/logoklein.png){kind=small}
Hallo,
ich möchte die Laufzzeit eines Algorithmus mit folgender Gleichung bestimmen:
t
= a * t(n^(1/k)) + log_2
wobei a und k Konstanten mit natürlichen Zahlen sind.
Ich möchte die Laufzeit der Gleichung aber _nicht_ durch Substitution bestimmen, also nicht sowas wie n = 2^x setzen oder ähnliches und dann per Mastertheorem. Darum geht es mir nicht.
Mein Ansatz ist folgender: Ich stelle eine Summe auf, bei der für jede Ebene des durch die Gleichung entstehenden Rekursionsbaumes die Anzahl der (unter)Probleme mit dem Aufwand pro Problem multipliziert wird. Die Höhe des Baumes ist - wenn ich mich nicht irre - die k-te superwurzel von n. Denn pro Rekursionsaufruf verringert sich n auf k-te wurzel. Das heißt ja, dass ich solange hintereinander Wurzeln ziehen muss, bis ich auf n=1 komme. Das Hintereinanderausführen dieses Prozesses nennt man wohl superwurzel (siehe Wikipedia).
Die Anzahl der (unter)Probleme pro "Ebene oder Stufe" des Baumes beträgt a^(i-te Ebene). Und der Aufwand für jedes dieser Probleme beträgt ja log_2(n'), wobei n' sich auf der i-ten Ebene bereits um i mal die k-te wurzel ziehen verringert hat, d.h. n' = (n^(1/(k^i)))
Daraus folgt dann (sorry an dieser Stelle, dass ichs nicht mit LaTeX machen kann):
Summe[von i=0 bis k-te superwurzel von n] a^i * log_2( n^[ 1/(k^i) ] )
Ich hab das mal versucht zu vereinfachen, indem ich das 1/(k^i) aus dem log_2 gezogen habe. Dadurch bleibt log_2 / (k^i) und man kann das log_2 vor die Summe ziehen. Dann erhält man:
log_2 * Summe[von i=0 bis k-te superwurzel von n] a^i / (k^i)
Und das ist nichts anderes als
log_2 * Summe[von i=0 bis k-te superwurzel von n] (a/k)^i
Soweit so gut. Daraus kann man dann schließen wenn a = k, dass die Laufzeit log_2 * k-te superwurzel ist, also in O(log*superwurzel) liegt.
Aber wie kriege ich die Laufzeit heraus, wenn a>k oder a<k ist?
Naja, ein großes Lob an alle, die es bis hierher geschafft haben
wär echt cool, wenn jemand von euch sich mit diesem mathematischen Zeugs ein bisschen auskennt.
ich möchte die Laufzzeit eines Algorithmus mit folgender Gleichung bestimmen:
t
= a * t(n^(1/k)) + log_2wobei a und k Konstanten mit natürlichen Zahlen sind.
Ich möchte die Laufzeit der Gleichung aber _nicht_ durch Substitution bestimmen, also nicht sowas wie n = 2^x setzen oder ähnliches und dann per Mastertheorem. Darum geht es mir nicht.
Mein Ansatz ist folgender: Ich stelle eine Summe auf, bei der für jede Ebene des durch die Gleichung entstehenden Rekursionsbaumes die Anzahl der (unter)Probleme mit dem Aufwand pro Problem multipliziert wird. Die Höhe des Baumes ist - wenn ich mich nicht irre - die k-te superwurzel von n. Denn pro Rekursionsaufruf verringert sich n auf k-te wurzel
. Das heißt ja, dass ich solange hintereinander Wurzeln ziehen muss, bis ich auf n=1 komme. Das Hintereinanderausführen dieses Prozesses nennt man wohl superwurzel (siehe Wikipedia).Die Anzahl der (unter)Probleme pro "Ebene oder Stufe" des Baumes beträgt a^(i-te Ebene). Und der Aufwand für jedes dieser Probleme beträgt ja log_2(n'), wobei n' sich auf der i-ten Ebene bereits um i mal die k-te wurzel ziehen verringert hat, d.h. n' = (n^(1/(k^i)))
Daraus folgt dann (sorry an dieser Stelle, dass ichs nicht mit LaTeX machen kann):
Summe[von i=0 bis k-te superwurzel von n] a^i * log_2( n^[ 1/(k^i) ] )
Ich hab das mal versucht zu vereinfachen, indem ich das 1/(k^i) aus dem log_2 gezogen habe. Dadurch bleibt log_2
/ (k^i) und man kann das log_2 vor die Summe ziehen. Dann erhält man:log_2
* Summe[von i=0 bis k-te superwurzel von n] a^i / (k^i)Und das ist nichts anderes als
log_2
* Summe[von i=0 bis k-te superwurzel von n] (a/k)^iSoweit so gut. Daraus kann man dann schließen wenn a = k, dass die Laufzeit log_2
* k-te superwurzel ist, also in O(log*superwurzel) liegt.Aber wie kriege ich die Laufzeit heraus, wenn a>k oder a<k ist?
Naja, ein großes Lob an alle, die es bis hierher geschafft haben
wär echt cool, wenn jemand von euch sich mit diesem mathematischen Zeugs ein bisschen auskennt.