www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
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
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenFunktionenRekursionsfunktion
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Funktionen" - Rekursionsfunktion
Rekursionsfunktion < Funktionen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Funktionen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Rekursionsfunktion: Einsetzen?
Status: (Frage) beantwortet Status 
Datum: 17:14 Mo 08.04.2013
Autor: bandchef

Aufgabe
Bestimmen Sie obere und untere Schranken für die folgende Rekursionsgleichungen von Algorithmen mit Hilfe der Iterationsmethode:

$T(1) = 1, T(n) = [mm] 2T\left(\frac{n}{4}\right)+\sqrt{n} \forall [/mm] n>1$

Hi Leute!

Die Aufgabe steht oben und ich habe gleich zu Beginn Probleme mit dem Einsetzen der Rekursionsformel. Wie geht das nun richtig? Stimmt es so:

$T(n) = [mm] 2T\left(\frac{n}{4}\right)+\sqrt{n} [/mm] = [mm] 2\left(2T\left(\frac{n}{8}\right)+\frac{\sqrt{n}}{4}\right)+\sqrt{n}$ [/mm]

Vielleicht kann mir ja jemand helfen?

        
Bezug
Rekursionsfunktion: Antwort
Status: (Antwort) fertig Status 
Datum: 17:31 Mo 08.04.2013
Autor: steppenhahn

Hallo,

 > Bestimmen Sie obere und untere Schranken für die folgende

> Rekursionsgleichungen von Algorithmen mit Hilfe der
> Iterationsmethode:

>

> [mm]T(1) = 1, T(n) = 2T\left(\frac{n}{4}\right)+\sqrt{n} \forall n>1[/mm] (*)



> Hi Leute!

>

> Die Aufgabe steht oben und ich habe gleich zu Beginn
> Probleme mit dem Einsetzen der Rekursionsformel. Wie geht
> das nun richtig? Stimmt es so:

>

> [mm]T(n) = 2T\left(\frac{n}{4}\right)+\sqrt{n} = 2\left(2T\left(\frac{n}{8}\right)+\frac{\sqrt{n}}{4}\right)+\sqrt{n}[/mm]


Das stimmt schon fast. Du musst aber beim zweiten Gleichheitszeichen überall $n/4$ statt $n$ in (*) einsetzen, daher lautet es richtig:

$... =  = [mm] 2\left(2T\left(\frac{n}{16}\right)+\frac{\sqrt{n}}{2}\right)+\sqrt{n}$. [/mm]

Als nächsten Schritt würde ich das zusammenfassen:

$= 4 [mm] T\left(\frac{n}{16}\right) [/mm] + [mm] \sqrt{n}\cdot \left(1 + \frac{1}{2}\right).$ [/mm]

Nun setzt du am besten noch einmal für [mm] $T\left(\frac{n}{16}\right)$ [/mm] den nächsten Rekursionsschritt ein und fasst noch einmal zusammen. Dann kannst du T(n) sicher allgemein angeben, wenn du $k$ Rekursionsschritte zurückgegangen wärst.


Viele Grüße,
Stefan

Bezug
                
Bezug
Rekursionsfunktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:34 Mo 08.04.2013
Autor: bandchef

Danke für dein ausführliche Hilfe!

Aber ich kann's mir nicht vorstellen, wie ich da jetzt die Funktion wieder in sich selbst einsetzen muss. Man muss das wieder einsetzen ja auch irgendwie hinschreiben könne, oder?  Es muss da ja irgendwie ein zwischen den beiden [mm] \frac{n}{4} [/mm] hinkommen weil ich ja nur so auf 16 im Nenner komme, aber dann würde ich ja auch [mm] n^2 [/mm] bekommen. Irgendwie raff ich das nicht :-(

Bezug
                        
Bezug
Rekursionsfunktion: Antwort
Status: (Antwort) fertig Status 
Datum: 17:39 Mo 08.04.2013
Autor: steppenhahn

Hallo,


> Aber ich kann's mir nicht vorstellen, wie ich da jetzt die
> Funktion wieder in sich selbst einsetzen muss. Man muss das
> wieder einsetzen ja auch irgendwie hinschreiben könne,
> oder?


Du hast in der letzten Gleichung [mm] $T\left(\frac{n}{16}\right)$ [/mm] stehen.

Deine Rekursionsgleichung lautet für alle $x [mm] \in \IN$: [/mm] $T(x) = 2 [mm] \cdot T\left(\frac{x}{4}\right) [/mm] + [mm] \sqrt{x}$. [/mm] (Ich habe mal zur Hilfestellung das n durch ein x ersetzt).

Nun musst du also $x = [mm] \frac{n}{16}$ [/mm] einsetzen, um [mm] $T\left(\frac{n}{16}\right)$ [/mm] zu erhalten! Was erhältst du?



Viele Grüße,
Stefan

Bezug
                                
Bezug
Rekursionsfunktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:45 Mo 08.04.2013
Autor: bandchef

Ok. Aber woher weiß ich, dass ich gerade [mm] $T(\frac{n}{16})$ [/mm] haben will? Ich könnte ja bspw. auch [mm] $T(\frac{n}{5})$ [/mm] haben wollen?!?!?

$ T(x) = 2 [mm] \cdot T\left(\frac{x}{4}\right) [/mm] + [mm] \sqrt{x} [/mm] = [mm] 2\left(2T\left(\frac{n}{4}\right)\cdot\left(\frac{n}{4} \right)\right)+\sqrt{n}$ [/mm]

Hier hab ich nun [mm] $2T\left(\frac{n}{4}\right)$ [/mm] in das T wieder eingesetzt... Aber das stimmt doch jetzt so nicht...

Bezug
                                        
Bezug
Rekursionsfunktion: Antwort
Status: (Antwort) fertig Status 
Datum: 17:55 Mo 08.04.2013
Autor: steppenhahn

Hallo,

 > Ok. Aber woher weiß ich, dass ich gerade [mm]T(\frac{n}{16})[/mm]

> haben will? Ich könnte ja bspw. auch [mm]T(\frac{n}{5})[/mm] haben
> wollen?!?!?


Nein, willst du nicht. Im letzten Schritt trat $T(n/16)$ auf.



> [mm]T(x) = 2 \cdot T\left(\frac{x}{4}\right) + \sqrt{x} = 2\left(2T\left(\frac{n}{4}\right)\cdot\left(\frac{n}{4} \right)\right)+\sqrt{n}[/mm]

>

> Hier hab ich nun [mm]2T\left(\frac{n}{4}\right)[/mm] in das T wieder
> eingesetzt... Aber das stimmt doch jetzt so nicht...

Ich sehen nicht, wieso du da n/4*n/4 bekommst.
Ich mach's dir nochmal vor:

1. Schritt:

$T(n)= 2 [mm] \cdot T\left(\frac{n}{4}\right) [/mm] + [mm] \sqrt{n}$. [/mm]   (*)

2. Schritt: Nun wollen wir [mm] $T\left(\frac{n}{4}\right)$ [/mm] ermitteln.

Wir kennen die Rekursionsgleichung: [mm] $\forall [/mm] x [mm] \in \IN: T(\red{x}) [/mm] = 2 [mm] \cdot T\left(\frac{\red{x}}{4}\right) [/mm] + [mm] \sqrt{\red{x}}$. [/mm]

Ich muss [mm] $\red{x = n / 4}$ [/mm] einsetzen, weil wir [mm] $T\left(\frac{n}{4}\right)$ [/mm] brauchen. Also:

[mm] $T\left(\red{\frac{n}{4}}\right) [/mm] = 2 [mm] \cdot T\left(\frac{\red{n/4}}{4}\right) [/mm] + [mm] \sqrt{\red{n/4}} [/mm] =2 [mm] \cdot T\left(\frac{n}{16}\right) [/mm] + [mm] \sqrt{n}/2$. [/mm]

DAS setzen wir jetzt in (*) ein:

$T(n)= 2 [mm] \cdot \left[2 \cdot T\left(\frac{n}{16}\right) + \sqrt{n}/2\right] [/mm] + [mm] \sqrt{n}$. [/mm]   (**)

3. Schritt: Du siehst, dass wir jetzt $T(n/16)$ brauchen, um die Gleichung weiter zurückzuverfolgen.



Viele Grüße,
Stefan

Bezug
                                                
Bezug
Rekursionsfunktion: Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 18:14 Mo 08.04.2013
Autor: bandchef

Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)

Aaaaaah! Jetzt denk ich hab ich das soweit verstanden: Hier jetzt der zweite Iterationsschritt:

$... = 2\left(2\left(2T\left(\frac{n}{256}\right)+\frac{\sqrt{n}}{8}\right) + \frac{\sqrt{n}}{2}}\right)+\sqrt{n} = 2^i \cdot T\left(\frac{n}{4^{i+1}}\right) + \sum^{i-1}_{k=0}\left( \frac{\sqrt{n}}{2^k} \right)$


Bezug
                                                        
Bezug
Rekursionsfunktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:17 Mo 08.04.2013
Autor: kaju35

Hallo Bandchef,

> Aaaaaah! Jetzt denk ich hab ich das soweit verstanden: Hier
> jetzt der zweite Iterationsschritt:
>  
> [mm]... = 2\left(2\left(2T\left(\frac{n}{256}\right)+\frac{\sqrt{n}}{8}\right) + \frac{\sqrt{n}}{2}}\right)+\sqrt{n} = 2^i \cdot T\left(\frac{n}{4^{i+1}}\right) + \sum^{i-1}_{k=0}\left( \frac{\sqrt{n}}{2^k} \right)[/mm]
>  
>  

Wie ich meine, musst Du [mm] $T\left(\frac{n}{64}\right)$ [/mm] als
nächstes bestimmen und nicht [mm] $T\left(\frac{n}{256}\right)$. [/mm]

Gruß
Kai

Bezug
                                                                
Bezug
Rekursionsfunktion: Laufzeit-Abschätzung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:55 Mo 08.04.2013
Autor: kaju35

Eingabefehler: "\left" und "\right" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "\left" und "\right" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)

Hallo Bandchef,

Also es ist ja :

$T\left(n\right)=2\cdot T\left(\frac{n}{4}\right)+\sqrt{n}$
$=2\cdot \left(2\cdot T\left(\frac{n}{16}\right)+\sqrt{\frac{n}{4}}\right)+\sqrt{n}$
$=2\cdot \left(2\cdot \left(2\cdot T\left(\frac{n}{64}\right)+\sqrt\frac{n}{16}\right)+\sqrt\frac{n}{4}\right)+\sqrt{n}$
$=8\cdot T\left(\frac{n}{64}\right)+4\cdot \frac{\sqrt{n}}{4}\right)+2\cdot \frac{\sqrt{n}}{2}\right)+\sqrt{n}$
$=8\cdot T\left(\frac{n}{64}\right)+3\cdot \sqrt{n}$
Allgemein ist $T(n)=2^{\log_4{n}}\cdot T\left(1\right)+\log_4{n}\cdot \sqrt{n}$
$=n^{\log_4{2}}\cdot T\left(1\right)+\log_4{n}\cdot \sqrt{n}=\sqrt{n}\cdot T\left(1\right)+\log_4{n}\cdot \sqrt{n}$

Daraus folgt mit $T(1)=1$ eine Laufzeit
von $T(n)=\sqrt{n}\cdot(1+\log_4{n})$

Gruß
Kai

Bezug
                                                                        
Bezug
Rekursionsfunktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:02 Mo 08.04.2013
Autor: bandchef

Hm, damit du auf n/64 kommst, musst du aber wieder n/4 aus dem ersten Iterationsschritt einsetzen. Ich hätte aber gedacht, dass man immer den vorhergehenden nehmen muss; hier also n/16?!?!?

Was stimmt nun?

Bezug
                                                                                
Bezug
Rekursionsfunktion: Iterationsschritt
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:15 Mo 08.04.2013
Autor: kaju35

Hallo Bandchef,

> Hm, damit du auf n/64 kommst, musst du aber wieder n/4 aus
> dem ersten Iterationsschritt einsetzen. Ich hätte aber

Ja, ist richtig. Ich nehme [mm] $\frac{n}{64}$ [/mm] wegen [mm] $T\left(\frac{n}{16}\right)=2\cdot T\left(\frac{\frac{n}{16}}{4}\right)+\sqrt{\frac{n}{16}}$ [/mm]

> gedacht, dass man immer den vorhergehenden nehmen muss;
> hier also n/16?!?!?

wo hast Du denn das her?

> Was stimmt nun?

zeige mir doch bitte mal, was aus dem Wurzelterm
wird, wenn Du immer den Wert aus dem vorherigen
Schritt nimmst!

Gruß
Kai


Bezug
                                                                                        
Bezug
Rekursionsfunktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:38 Mo 08.04.2013
Autor: bandchef

Das heißt also, man muss jeden Iterationsschritt in die durch die Aufgabe angegebene Ursprüngliche Rekursionsformel einsetzen?

Die allgemeine Form sieht bei mir nun so aus: [mm] $2^i \cdot T\left(\frac{n}{4^i}\right)+i\cdot \sqrt{n}$ [/mm]

Richtig?

Jetzt muss ich doch über die Rekursionsbasis die Formel weiter vereinfachen: [mm] $n=4^i \Leftrightarrow log_2(n) [/mm] = 2i [mm] \Rightarrow \frac12 log_2(n) [/mm] = i$

Richtig?

Eingesetzt: [mm] 2^{\frac12 log_2(n)} [/mm] + [mm] \frac12 log_2(n) \cdot \sqrt{n} [/mm] = [mm] \sqrt{n} [/mm] + [mm] \frac12 log_2(n) \sqrt{n}$ [/mm]

Bezug
                                                                                                
Bezug
Rekursionsfunktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:52 Mo 08.04.2013
Autor: kaju35

Hallo Bandchef,

> Das heißt also, man muss jeden Iterationsschritt in die
> durch die Aufgabe angegebene Ursprüngliche
> Rekursionsformel einsetzen?

Sprachlich sehe ich keinen Sinn darin, den Iterationsschritt
einzusetzen, aber ich denke, Du meinst das Richtige.

Gruß
Kai


Bezug
                                                                                                        
Bezug
Rekursionsfunktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:58 Mo 08.04.2013
Autor: bandchef

Schau dir bitte meine vorherige (editierte) Antwort an. Ich hab da jetzt mal alles vorgerechnet wie ich es hier stehen hab. Das wäre nett!

Bezug
                                                                                                        
Bezug
Rekursionsfunktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:05 Mo 08.04.2013
Autor: bandchef

Ich meinte, dass ich hier, das n/4 in die in der Aufgabenstellung angegebene Formel einsetzen muss. Dann ergibt sich ja ein n/16. Dieses n/16 setze ich wieder in die Aufgabenstellung angegebene Formel ein. Das dann berechnete n/64 wieder in diese Formel.

Ich hab BISHER immer das n/4, n/16 und n/64 in den jeweiligen Schritt DAVOR eingesetzt. Ich hatte bspw. bei n/64 sowas stehen: [mm] $T(\frac{\frac{n}{16}}{16})$ [/mm] Was zu n/265 führte!

Bezug
                                                                                                
Bezug
Rekursionsfunktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:17 Mo 08.04.2013
Autor: kaju35

Hallo Bandchef,

> Die allgemeine Form sieht bei mir nun so aus: [mm]2^i \cdot T\left(\frac{n}{4^i}\right)+i\cdot \sqrt{n}[/mm]
>  
> Richtig?

[ok]

>  
> Jetzt muss ich doch über die Rekursionsbasis die Formel
> weiter vereinfachen: [mm]n=4^i \Leftrightarrow log_2(n) = 2i \Rightarrow \frac12 log_2(n) = i[/mm]
>  
> Richtig?

[ok]

>  
> Eingesetzt: [mm]2^{\frac12 log_2(n)}[/mm] + [mm]\frac12 log_2(n) \cdot \sqrt{n}[/mm]
> = [mm]\sqrt{n}[/mm] + [mm]\frac12 log_2(n) \sqrt{n}$[/mm]  

Absolut richtig.

Gruß
Kai

Bezug
                                                                                                        
Bezug
Rekursionsfunktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:19 Mo 08.04.2013
Autor: bandchef

Danke für deine Hilfe! Hat mir Spaß gemacht mit dir die Lösung zu erarbeiten!

Bezug
                                                                                                        
Bezug
Rekursionsfunktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:30 Mo 08.04.2013
Autor: bandchef

mir ist noch ein Fehler aufgefallen:

$ [mm] 2^{\frac12 log_2(n)} \cdot T\left(\frac{n}{4^{\frac12 log_2(n)}}\right)+\frac12 log_2(n)\cdot \sqrt{n} [/mm] = [mm] \sqrt{n} [/mm] + T(n/n) + [mm] {\frac12 log_2(n)}\cdot \sqrt{n} [/mm] = [mm] \sqrt{n} [/mm] + 1 + [mm] {\frac12 log_2(n)}\cdot \sqrt{n}$ [/mm]

So sollte es doch jetzt passen, oder?

Aber zu deiner Lösung ist meine Lösung jetzt doch unterschiedlich geworden, oder?

Bezug
                                                                                                                
Bezug
Rekursionsfunktion: Schranken
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 10:16 Di 09.04.2013
Autor: kaju35

Hallo Bandchef,

> mir ist noch ein Fehler aufgefallen:
>  
> [mm]2^{\frac12 log_2(n)} \cdot T\left(\frac{n}{4^{\frac12 log_2(n)}}\right)+\frac12 log_2(n)\cdot \sqrt{n} = \sqrt{n} + T(n/n) + {\frac12 log_2(n)}\cdot \sqrt{n} = \sqrt{n} + 1 + {\frac12 log_2(n)}\cdot \sqrt{n}[/mm]
>  
> So sollte es doch jetzt passen, oder?

Es muss heißen : [mm]2^{\frac12 log_2(n)} \cdot T\left(\frac{n}{4^{\frac12 log_2(n)}}\right)+\frac12 log_2(n)\cdot \sqrt{n} = \sqrt{n} \red\cdot T(\frac{n}{n}) + {\frac12 log_2(n)}\cdot \sqrt{n} = \sqrt{n} +{\frac12 log_2(n)}\cdot \sqrt{n}[/mm]

>  
> Aber zu deiner Lösung ist meine Lösung jetzt doch
> unterschiedlich geworden, oder?

Mit [mm] $log_4(n)=\frac{1}{2}\cdot log_2(n)$ [/mm] sollte es passen.

Bleiben noch die obere und untere Schranke anzugeben!

Gruß
Kai

Bezug
                                                                                                                        
Bezug
Rekursionsfunktion: Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 16:46 Di 09.04.2013
Autor: bandchef

Ich komme übrigens nun auch auf deine angegebene Lösung. Ich hatte versehentlich den Malpunkt durch ein Pluszeichen ersetzt. Jetzt stimmt aber alles :-)

Die Sache mit der oberen und unteren Schranke an der Stelle hab ich auch noch nicht so ganz verstanden. Was ich hier nun berechnet habe ist doch die exakte Schranke, oder?

Ist es nicht so, dass bei einer exakten Schranke, die obere und untere Schranke zusammenfällt und ich so doch eigentlich gar nix angeben brauche?

Kannst du mir wieder weiterhelfen?

Bezug
                                                                                                                                
Bezug
Rekursionsfunktion: Schranke
Status: (Antwort) fertig Status 
Datum: 17:04 Di 09.04.2013
Autor: kaju35

Hallo Bandchef,

> Die Sache mit der oberen und unteren Schranke an der Stelle
> hab ich auch noch nicht so ganz verstanden. Was ich hier
> nun berechnet habe ist doch die exakte Schranke, oder?

Ich frage mich auch, wofür der Aufgabensteller noch Schranken
braucht, wenn wir Doch einen exakten Wert für die
Laufzeit angeben können.

>  
> Kannst du mir wieder weiterhelfen?

Manchmal braucht man (in erster Linie Informatiker) eben
Schranken, um das asymptotische Verhalten der Laufzeit besser
einordnen zu können.

Wie auch immer...

Als untere Schranke halte ich eine Funktion für
geeignet, die für [mm] $n\to\infty$ [/mm] größer als c und kleiner
als [mm] $\sqrt{n}\cdot (1+\log_4(n))$ [/mm] ist.

Zur oberen Schranke überlege ich mir, dass [mm] $\sqrt{n}$ [/mm] schneller
wächst als [mm] $1+\log_4(n)$, [/mm] weswegen folgt, dass...

Gruß
Kai

Bezug
                                                                                                                                        
Bezug
Rekursionsfunktion: Obere und untere Schranke
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:18 Mi 10.04.2013
Autor: kaju35

Hallo Bandchef,

bist Du an der Lösung der Aufgabe noch interessiert?

Nur als Vorschlag :

Eine untere Schranke wäre z.B. gegeben durch
[mm] $u(n)=\sqrt{n}$, [/mm] weil es zwischen einer Konstanten und
[mm] $\sqrt{n}\cdot(1+\log_4(n))$ [/mm] verläuft.

Mein zweiter Tipp ist so zu verstehen, dass wenn
[mm] $\sqrt{n}$ [/mm] rascher als [mm] $1+\log_4(n)$ [/mm] wächst, dann auch
[mm] $\sqrt{n}\cdot \sqrt{n}$ [/mm] als [mm] $\sqrt{n}\cdot(1+\log_4(n))$. [/mm]

Somit ist [mm] $o(n)=\sqrt{n}\cdot\sqrt{n}=n$ [/mm] eine geeignete obere Schranke.

Gruß
Kai


Bezug
        
Bezug
Rekursionsfunktion: Tipps zu TEX (Zwischenr. etc.)
Status: (Antwort) fertig Status 
Datum: 18:39 Mo 08.04.2013
Autor: Al-Chwarizmi


> [mm]T(1) = 1, T(n) = 2T\left(\frac{n}{4}\right)+\sqrt{n} \forall n>1[/mm]


Hallo bandchef,

nur ein ganz kleiner Tipp zu $\ T_EX$ betr. Zwischen-
räume in Formeln, den hoffentlich auch viele andere
lesen werden:

Deine obige $\ T_EX$ - Zeile hast du dir bestimmt etwas
anders vorgestellt, als sie wirklich erscheint.
Vielleicht etwa so:

  [mm]T(1) = 1\ ,\quad T(n)\ =\ 2\ *T\left(\frac{n}{4}\right)+\sqrt{n}\qquad (\forall n>1)[/mm]

(bitte auf obige Formelzeile klicken, um zu sehen,
wie ihre genaue [mm] $\green{ T_EX}$- [/mm] Syntax aussieht !)


Wichtig ist vor allem, zu wissen, dass die
Zwischenräume, die man in einem TEX - Code
lässt, von TEX nicht als solche beachtet werden.
Man muss sie selber planen und definieren.
Im Formeleditor werden diese Möglichkeiten im
letzten Abschnitt "Platz zwischen den Zeichen"
erläutert.

LG ,  Al-Chw.


(Wer sich auch bezüglich Fett- und Kursivschrift etc.
in eigenen Beiträgen noch nicht so recht auskennt,
sollte auch mal den Quelltext dieses Artikels
angucken anschauen)


  

Bezug
                
Bezug
Rekursionsfunktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:08 Mi 10.04.2013
Autor: ChopSuey

Hallo Al,

ich nutze als Nostalgiker nach wie vor den klassischen Editor und bei mir sieht das auch ohne erzwungene Zwischenräume ganz gut aus:

$ f(x) = 2x - 1 $ (siehe Code)

Scheinbar ist das etwas, das erst mit dem neuen Formeleditor hinzukam?

Viele Grüße,
ChopSuey

Bezug
                        
Bezug
Rekursionsfunktion: Zwischenräume
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:16 Mi 10.04.2013
Autor: Al-Chwarizmi


> Hallo Al,
>  
> ich nutze als Nostalgiker nach wie vor den klassischen
> Editor und bei mir sieht das auch ohne erzwungene
> Zwischenräume ganz gut aus:
>  
> [mm]f(x) = 2x - 1[/mm] (siehe Code)
>  
> Scheinbar ist das etwas, dass erst mit dem neuen
> Formeleditor hinzukam?
>  
> Viele Grüße,
>  ChopSuey


Hallo,

ich glaub' ich brauche auch den ganz "normalen"
Editor. Bei ganz einfachen Formeln wie etwa

   $\ f(x)=2x-1$

ist auch alles in Ordnung; aber wenn man etwa
Bedingungen angeben will wie

   $\ f(x)=2x-1       [mm] (x\le0)$ [/mm]

werden die Zwischenräume, die ich im Code zwar
durchaus gesetzt habe, nicht beachtet - und das
Ergebnis ist unschön. Deshalb brauche ich in dieser
Zeile ein  \qquad , um wirklich den gewünschten
Zwischenraum zu erhalten:

   $\ [mm] f(x)=2x-1\qquad(x\le0)$ [/mm]

Diesen Zwischenraum könnte man natürlich auch
erzeugen, indem man die Zeile in zwei Teilformeln
zerlegt. Das finde ich aber insbesondere für das
nachträgliche Kopieren und Bearbeiten von Formel-
zeilen äußerst lästig, wenn mehrere Bestandteile
in einer einzigen Zeile nebeneinander stehen und
nicht stets wieder auseinandergerissen werden sollen.

Auch etwa die Zeile

   $\ [mm] a*b=0\gdw a=0\vee [/mm] b=0$

gefällt mir etwas "lockerer" notiert viel besser:

   $\ a*b\ =\ [mm] 0\quad\gdw\quad a\,=\,0\ [/mm] \ [mm] \vee\ [/mm] \ [mm] b\,=\,0$ [/mm]

Durch gezielten Einsatz von Zwischenräumen kann
man manche Formeln deutlich lesbarer gestalten.
Zugegeben, dies bedeutet auch etwas mehr Arbeit,
aber es ist vor allem auch Übungssache.
Das Ganze sollte aber vor allem ein Tipp sein an
alle, die die Zwischenraumzeichen überhaupt noch
nie angetroffen oder ihre Verwendung in Betracht
gezogen haben.   :-)

LG ,   Al-Chw.



Bezug
                        
Bezug
Rekursionsfunktion: Unschuldig
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 09:53 Do 11.04.2013
Autor: wieschoo

Hi,

ich glaube kaum, dass es am neuen Editor liegt. Der Formelquelltext wird 1:1 in LaTeX geschickt. LaTeX selbst ignoriert die Leerzeichen meiner Erfahrung nach, was auch gut so ist.

Und [mm] f(x) = 2x - 1 [/mm] geht hier ebenfalls, da LaTeX hier geeignet die Abstände setzt.
Es ist jedoch eine gute Idee: $ \ [mm] f(x)=2x-1\qquad(x\le0) [/mm] $ noch mit in die Beispielrubrik aufzunehmen.

gruß
wieschoo

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Funktionen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]