Master-Theorem < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Leiten Sie eine asymptotisch scharfe Schranke für folgende Funktion her:
T(n) = [mm] 2T((2^{(log_{8} n^{9})-3})^{\bruch{1}{3}})+2^{log_{2]}n} [/mm] |
Diese Aufgabe wurde wie folgt gelöst:
= [mm] 2T((2^{3(log_{8} n)-1}))+n
[/mm]
[mm] =2T((n^{log_{8}2})^{3}*\bruch{1}{2})+n
[/mm]
womit ich auch schon bei dem Teil bin, den ich nicht verstehe. Wo kommt jetzt das [mm] "*\bruch{1}{2}" [/mm] her und wo bleibt die "hoch -1" ab?
Der letzte Schritt
[mm] =2T(\bruch{1}{2}n)+n
[/mm]
und die dann folgende Herleitung der Schranke sind mir dann wieder klar, nur eben der oben beschriebene Schritt nicht... :(
|
|
| |
|
Hallo LordHorst!
> Leiten Sie eine asymptotisch scharfe Schranke für folgende
> Funktion her:
> T(n) = [mm]2T((2^{(log_{8} n^{9})-3})^{\bruch{1}{3}})+2^{log_{2]}n}[/mm]
>
> Diese Aufgabe wurde wie folgt gelöst:
> = [mm]2T((2^{3(log_{8} n)-1}))+n[/mm]
>
> [mm]=2T((n^{log_{8}2})^{3}*\bruch{1}{2})+n[/mm]
>
> womit ich auch schon bei dem Teil bin, den ich nicht
> verstehe. Wo kommt jetzt das [mm]"*\bruch{1}{2}"[/mm] her und wo
> bleibt die "hoch -1" ab?
Bist du sicher, dass du nicht irgendwo die 2 und das n vertauscht hast? Naja, jedenfalls kann ich dir sagen, wo [mm] \bruch{1}{2} [/mm] herkommt. Und zwar gilt doch:
[mm] 2^{3(log_{8} n)-1}=2^{3(log_8n)}*2^{-1}=2^{3(log_8n)}*\frac{1}{2}
[/mm]
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:53 Di 27.02.2007 | | Autor: | LordHorst |
Ah, jetzt ist mir alles klar! Vielen Dank! :)
PS: Das n und die 2 hab ich schon "vertauscht", aber es gilt ja [mm] a^{log_{b} c} [/mm] = [mm] c^{log_{b} a}, [/mm] von daher sollte das eigentlich korrekt sein :D .
|
|
|
|
.
