Substituation Laufzeitanalyse < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 12:53 Mo 15.03.2021 | | Autor: | b.reis |
| Aufgabe | [mm] T(\wurzel{n})+1
[/mm]
Lösen Sie diese Rekursionsgleichung mit Hilfe des Mastertheorems
Meine Frage ist, gibt es allgemein nicht nur mit der Wurzel andere Möglichkeiten zur Substitution? |
Also das Mastertheorem sieht so aus:
T=Time
a sind alle Untereinheiten, f(n) ist die Laufzeit für Operationen wie + und -
die von der Rekursion gebildet werden, T(n) ist die Größe dieser Operationen.
Gegeben beispielsweise [mm] T(\wurzel{n})+1
[/mm]
[mm] T(n)=\begin{cases} c, & \mbox{für } n \mbox{ c<=0} \\ a*T(\bruch{n}{b})+f(n), & \mbox{für } n \mbox{ c>0} \end{cases}
[/mm]
Gesucht sind a,b, d =log (n) in f(n)
T(n) [mm] \in \begin{cases} n^d , & \mbox{für }d \mbox{>logb(a)} \\ n^{d}*log (n) , & \mbox{für } d \mbox{ =logb(a)} \\ n^{logb(a)} , & \mbox{für } d \mbox{
die Aufgabe [mm] T(\wurzel{n})+1 [/mm] wird so gelöst:
n = [mm] 2^m [/mm] m = [mm] log_{2}(n) [/mm] eingesetzt für n in T(n) [mm] =\wurzel[2]{n}=\wurzel[2]{2^{m}} [/mm] = [mm] 2^{\bruch{m}{2}}
[/mm]
Hilfsfunktion erstellt damit ich an den Exponenten komme also wieder den Log = [mm] \bruch{m}{2}
[/mm]
Hilfsfunktion S(m) = [mm] \bruch{m}{2} [/mm]
jetzt gibt es ein a=1 b=2 d=der Exponent von f(n)=1 [mm] n^0=1 [/mm] --> d=0
[mm] a*T(\bruch{n}{b})+f(n)
[/mm]
[mm] log_{b}(a) [/mm] = 0 da [mm] 2^0 [/mm] =1=a damit ist [mm] O(S(m))\in (d=0=0=log_{b}(a))
[/mm]
-> Fall [mm] d=log_{b}(a)
[/mm]
[mm] n^d [/mm] *log(n)
[mm] n^0 [/mm] *log(n) -> S(m) [mm] \in [/mm] O(log(m))
Rücksubstitution
T(n) [mm] \in [/mm] O(log(log(n))
Meine Frage ist, vielleicht seht Ihr das schneller als ich, gibt es noch andere Möglichkeiten für eine Substitution um auf den Exponenten zu kommen der den [mm] \bruch{n}{b} [/mm] für [mm] T(\bruch{n}{b}) [/mm] am Ende ergibt. oder geht das nur mit der Wurzel ?
Ich frage für die Prüfungsvorbereitung :)
Danke
Benni
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:39 Sa 20.03.2021 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
