www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Navigation
 Startseite...
 Suchen
 Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Uni-Analysis-Sonstiges" - Substituation Laufzeitanalyse
Substituation Laufzeitanalyse < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Substituation Laufzeitanalyse: log (n) Master-Theorem
Status: (Frage) überfällig Status 
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

        
Bezug
Substituation Laufzeitanalyse: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:39 Sa 20.03.2021
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]