Master Theorem < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:43 Mo 14.01.2013 | | Autor: | bandchef |
| Aufgabe | Beweisen Sie folgende Aussagen mit Hilfe der Master-Methode:
Sei $T(1) = 1, T(n) = [mm] 3T\left(\frac{n}{4}\right)+n \cdot [/mm] log(n)$ für alle $n>1$, dann: $T(n) = [mm] \Theta(n\cdot [/mm] log(n))$ |
Hi Leute!
Könnt ihr mir hier helfen? Ich bin da echt ziemlich ratlos!
Das Master-Theorem besagt ja laut Wikipedia und meinen Unterlagen, dass man 3 Fälle überprüfen muss.
1. Fall:
Aus der Angabe ergeben sich $b=4$ und $a=3$ sowie [mm] $f(n)=n\cdot [/mm] log(n)$
1. Bedingung:
[mm] $\Rightarrow [/mm] f(n) [mm] \in O\left(n^{log_b(a) - \epsilon}\right)$ [/mm] für ein [mm] $\epsilon [/mm] > 0$
[mm] $\Leftrightarrow n\cdot [/mm] log(n) [mm] \in O\left(n^{log_4(3) -\epsilon}\right)$
[/mm]
[mm] $\Leftrightarrow [/mm] n [mm] \cdot [/mm] log(n) [mm] \in O\left(n^{0,792...-\epsilon}\right)$
[/mm]
Gegenüber dem Beispiel aus der Wikipedia geht meine Übungsaufgabe aber leider nicht gerade auf.
Frage: Wie kann ich nun ausrechnen, wo sich nun $ n [mm] \cdot [/mm] log(n)$ befindet? Liegt es in [mm] $O\left(n^{0,792...-\epsilon}\right)$ [/mm] oder liegt es doch nicht drin?
Könnt ihr mir helfen?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:52 Mo 14.01.2013 | | Autor: | bandchef |
Kann mir wirklich niemand helfen?
|
|
|
| |
|
Hallo bandchef,
nicht drängeln, ist doch gerade mal eine Stunde her ....
Welche Erwartungshaltung hast du denn an den MR?
Die solltest du mal überdenken!
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:19 Mo 14.01.2013 | | Autor: | bandchef |
Entschuldige Bitte...
Es war ja nicht böse gemeint. Ich brenn da nur grad drauf endlich die Lösung zu bekommen, weil das eine Aufgabe ist, die ich schon seit langem vor mir her schiebe...
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:23 Mo 14.01.2013 | | Autor: | felixf |
Moin!
> Frage: Wie kann ich nun ausrechnen, wo sich nun [mm]n \cdot log(n)[/mm]
> befindet? Liegt es in [mm]O\left(n^{0,792...-\epsilon}\right)[/mm]
> oder liegt es doch nicht drin?
$n [mm] \log [/mm] n$ liegt in [mm] $O(n^\alpha)$ [/mm] genau dann, wenn [mm] $\alpha [/mm] > 1$ gilt.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:54 Mo 14.01.2013 | | Autor: | bandchef |
Da ich aber [mm] $\alpha [/mm] > 1$ nicht mehr erreichen werde, da der Exponente eh schon kleiner 1 und eine Zahl [mm] $\epsilon [/mm] >0$ subtrahiert werden soll, wird's auch nie in der oberen Schranke liegen. Was ist mit dem log(n)? Ich gehe schon richtig in der Annahme, dass bei so Laufzeitabschätzungen nur die höchste Potenz ausschlaggebend ist, weshalb das log(n) unter den Tisch fällt.
Soweit richtig?
Dann zum 2. Fall:
[mm] $\Rightarrow [/mm] n [mm] \cdot [/mm] log(n) = [mm] \Theta \left(n^{log_4(3)}\right)$
[/mm]
[mm] $\Leftrightarrow [/mm] n [mm] \cdot [/mm] log(n) = [mm] \Theta \left(n^{0,79}\right)$
[/mm]
Der 2. Fall kümmert sich ja um die exakte Schrank. Wenn es exakt sein muss, werde ich wohl auch ein Gleichheitszeichen verwenden müssen, oder? Wie man hier also sehen kann, ist dann wohl die Funktion auf der linken Seite nicht das gleiche wie das Argument vom Landausymbol wodurch der 2. Fall auch nicht zu trifft.
Soweit richtig?
Dann zum 3. Fall:
1. Bedingung:
[mm] $\Rightarrow [/mm] n [mm] \cdot [/mm] log(n) [mm] \geq \Omega \left(n^{log_4(3)+\epsilon}\right)$
[/mm]
[mm] $\Leftrightarrow [/mm] n [mm] \cdot [/mm] log(n) [mm] \geq \Omega \left(n^{0,79+\epsilon}\right)$
[/mm]
Für einen passend gewählten Wert von [mm] $\epsilon [/mm] = 0,21$ liegt doch nun $n [mm] \cdot [/mm] log(n)$ drin, oder?
Zusätzlich muss nun noch gelten:
[mm] $\Rightarrow [/mm] a [mm] \cdot f\left( \frac{n}{b}\right) \leq [/mm] c [mm] \cdot [/mm] f(n)$ für $c>1$ und alle $n [mm] \geq n_0$
[/mm]
[mm] $\Leftrightarrow [/mm] 3 [mm] \cdot \frac{n}{4} \cdot \log\left(\frac{n}{4}\right) \leq [/mm] c [mm] \cdot [/mm] n [mm] \cdot [/mm] log(n)$
[mm] $\Leftrightarrow \frac34 \log\left(\frac{n}{4}\right) \leq [/mm] c [mm] \cdot [/mm] log(n)$
[mm] $\Leftrightarrow \frac{\frac34 log(n)-\frac32}{log(n)} \leq [/mm] c$
Und hier weiß ich aber jetzt nicht mehr weiter? stimmt das überhaupt noch alles?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:14 Mo 14.01.2013 | | Autor: | Helbig |
Hallo bandchef,
Wir haben die Gleichung $T(n) = [mm] 3T\left({n \over 4}\right) [/mm] + [mm] n\log [/mm] n$ und sollen mit dem master theorem [mm] $T(n)\in \Theta(n\log [/mm] n)$ zeigen. Hierfür kommt, wenn überhaupt, nur Fall 3 in Frage, da die anderen beiden Fälle anderes behaupten. Dazu überprüfe mal die beiden Bedingungen aus Fall 3, und melde Dich, wenn Du auf Schwierigkeiten stößt.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:48 Di 15.01.2013 | | Autor: | bandchef |
Hallo helbig!
> Hierfür kommt, wenn überhaupt, nur Fall 3 in Frage, da die anderen beiden Fälle anderes behaupten.
Wie kann man ohne etwas zu rechnen schon sagen, dass nur 3 Fall in Frage kommen kann? Ich habe immer gedacht, man muss alle 3 Fälle durchmachen um den Fall herauszufinden der passt bzw. auch herauszufinden, dass das Master-Theorem nicht anzuwenden ist.
Aber gut. Ich wende jetzt mal die zwei Bedingungen des dritten Falls auf die Gleichung an:
Aus der Rekursionsgleichung $T(n) = [mm] 3T\left(\frac{n}{4}\right)+n\cdot [/mm] log(n)$ kann man nun $a=3$, $b=4$ und $f(n) = n [mm] \cdot [/mm] log(n)$ ablesen.
1. Bedingung:
[mm] $\Rightarrow [/mm] f(n) = [mm] \Omega\left(n^{log_b(a)+\epsilon}\right)$ [/mm] für ein [mm] $\epsilon [/mm] > 0$
[mm] $\Leftrightarrow n\cdot [/mm] log(n) = [mm] \Omega\left(n^{log_4(3)+\epsilon}\right)$
[/mm]
[mm] $\Leftrightarrow n\cdot [/mm] log(n) = [mm] \Omega\left(n^{0,793+\epsilon}\right)$ [/mm] mit passendem [mm] \epsilon [/mm] gilt:
[mm] $\Leftrightarrow [/mm] n = [mm] \Omega(n)$
[/mm]
Ist die Schlussfolgerung der 1. Bedingung korrekt? Mit einem passenden [mm] \epsilon [/mm] bekomme ich [mm] n^1. [/mm] In der $f(n)$ ist [mm] n^1 [/mm] die höchste Potenz. Dieser logarithmische Anteil wird doch in dieser O-Notation vernachlässigt, wodurch doch nun die Funktion $f(n)$ in $ [mm] \Omega(n)$ [/mm] liegt, oder?
Andere zusätzliche Frage: In Wikipedia wird die 1. Bedingung folgendermaßen angegeben: [mm] $\Rightarrow [/mm] f(n) [mm] \in \Omega\left(n^{log_b(a)+\epsilon}\right)$. [/mm] In meinem Skript ist das [mm] \in [/mm] aber ein "="? Was ist nun richtig?
So, nun zur 2. Bedingung:
[mm] $\Rightarrow [/mm] a [mm] \cdot f\left(\frac{n}{b}\right) \leq [/mm] c [mm] \cdot [/mm] f(n)$
[mm] $\Leftrightarrow [/mm] 3 [mm] \cdot \left( \frac{n}{4} \cdot log\left(\frac{n}{4}\right) \right) \leq [/mm] c [mm] \cdot [/mm] n [mm] \cdot [/mm] log(n)$
[mm] $\Leftrightarrow \frac34\left( log(n) - log(4) \right) \leq [/mm] c [mm] \cdot [/mm] log(n)$
[mm] $\Leftrightarrow \frac34 [/mm] log(n) - [mm] \frac32 \leq [/mm] c [mm] \cdot [/mm] log(n)$ ich wähle nun $c = [mm] \frac34$
[/mm]
[mm] $\Leftrightarrow \frac34 [/mm] log(n) - [mm] \frac32 \leq \frac34 \cdot [/mm] log(n)$
Da die letzte Zeile richtig ist, kann ich nun durch das Master-Theorem wohl folgern, dass $T(n) = [mm] \Theta\left(f(n)\right) [/mm] = [mm] \Theta\left(n \cdot log(n)\right)$ [/mm] gilt.
Soweit richtig?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:11 Di 15.01.2013 | | Autor: | Helbig |
Hallo bandchef,
> > Hierfür kommt, wenn überhaupt, nur Fall 3 in Frage, da
> > die anderen beiden Fälle anderes behaupten.
>
>
> Wie kann man ohne etwas zu rechnen schon sagen, dass nur 3
> Fall in Frage kommen kann? Ich habe immer gedacht, man muss
> alle 3 Fälle durchmachen um den Fall herauszufinden der
> passt bzw. auch herauszufinden, dass das Master-Theorem
> nicht anzuwenden ist.
Vergleiche die Behauptung der Aufgabe mit den Folgerungen jedes der drei Fälle. Da paßt nur der dritte. Wenn Du zeigen willst, daß eine gegebene Folge keine der drei Bedingungen erfüllt, mußt Du tatsächlich von allen drei Bedingungen zeigen, daß sie nicht erfüllt sind. Aber seien wir mal optimistisch!
>
>
> Aber gut. Ich wende jetzt mal die zwei Bedingungen des
> dritten Falls auf die Gleichung an:
Prima!
>
> Aus der Rekursionsgleichung [mm]T(n) = 3T\left(\frac{n}{4}\right)+n\cdot log(n)[/mm]
> kann man nun [mm]a=3[/mm], [mm]b=4[/mm] und [mm]f(n) = n \cdot log(n)[/mm] ablesen.
Richtig!
>
> 1. Bedingung:
> [mm]\Rightarrow f(n) = \Omega\left(n^{log_b(a)+\epsilon}\right)[/mm]
> für ein [mm]\epsilon > 0[/mm]
> [mm]\Leftrightarrow n\cdot log(n) = \Omega\left(n^{log_4(3)+\epsilon}\right)[/mm]
>
> [mm]\Leftrightarrow n\cdot log(n) = \Omega\left(n^{0,793+\epsilon}\right)[/mm]
> mit passendem [mm]\epsilon[/mm] gilt:
> [mm]\Leftrightarrow n = \Omega(n)[/mm]
>
> Ist die Schlussfolgerung der 1. Bedingung korrekt? Mit
> einem passenden [mm]\epsilon[/mm] bekomme ich [mm]n^1.[/mm] In der [mm]f(n)[/mm] ist
> [mm]n^1[/mm] die höchste Potenz. Dieser logarithmische Anteil wird
> doch in dieser O-Notation vernachlässigt, wodurch doch nun
> die Funktion [mm]f(n)[/mm] in [mm]\Omega(n)[/mm] liegt, oder?
Das ist zwar richtig, aber für meinen Geschmack nicht ausreichend begründet.
Erstens: Du setzt offensichtlich [mm] $\epsilon [/mm] = 1 - [mm] \log_4 3\,.$ [/mm] Das könntest Du doch auch einfach schreiben. Und begründen, warum [mm] $\epsilon$ [/mm] positiv ist.
Zweitens: Das mit dem Vernachlässigen ist mir zu schwammig. Dies mag für die O-Notation gelten, aber hier haben wir die [mm] $\Omega$-Notation. [/mm] Und dieses "Vernachlässigen" gilt bestimmt nicht für jedes Landau-Symbol.
Du willst also [mm] $n\log [/mm] n = [mm] \Omega [/mm] (n)$ zeigen. Und das bedeutet nach Wikipedia:
[mm] $\liminf_{n\to\infty} {n\log n \over n} [/mm] > [mm] 0\,.$
[/mm]
Dieses wiederum folgt aus $ [mm] {n\log n \over n} \to \infty$ [/mm] für [mm] $n\to\infty\,.$
[/mm]
> Andere zusätzliche Frage: In Wikipedia wird die 1.
> Bedingung folgendermaßen angegeben: [mm]\Rightarrow f(n) \in \Omega\left(n^{log_b(a)+\epsilon}\right)[/mm].
> In meinem Skript ist das [mm]\in[/mm] aber ein "="? Was ist nun
> richtig?
Ganz eindeutig [mm] $\in$. [/mm] Warum? Damit behält das Gleichheitszeichen seine Bedeutung, nämlich, daß die beiden Ausdrücke links und rechts von "=" Namen ein und desselben mathematischen Objekts sind. Links steht hier die Bezeichnung einer Funktion auf [mm] $\IN$, [/mm] rechts eine Menge solcher Funktionen. Zwei verschiedene Sachen! Leider ist auch die andere, verwirrende Schreibweise verbreitet. Wenn man sowas liest, sollte man also in Gedanken stets = durch [mm] $\in$ [/mm] ersetzen.
>
>
> So, nun zur 2. Bedingung:
> [mm]\Rightarrow a \cdot f\left(\frac{n}{b}\right) \leq c \cdot f(n)[/mm]
>
> [mm]\Leftrightarrow 3 \cdot \left( \frac{n}{4} \cdot log\left(\frac{n}{4}\right) \right) \leq c \cdot n \cdot log(n)[/mm]
>
> [mm]\Leftrightarrow \frac34\left( log(n) - log(4) \right) \leq c \cdot log(n)[/mm]
>
> [mm]\Leftrightarrow \frac34 log(n) - \frac32 \leq c \cdot log(n)[/mm]
> ich wähle nun [mm]c = \frac34[/mm]
> [mm]\Leftrightarrow \frac34 log(n) - \frac32 \leq \frac34 \cdot log(n)[/mm]
>
> Da die letzte Zeile richtig ist, kann ich nun durch das
> Master-Theorem wohl folgern, dass [mm]T(n) = \Theta\left(f(n)\right) = \Theta\left(n \cdot log(n)\right)[/mm]
> gilt.
>
> Soweit richtig?
Ja! Hier hast Du wohl stillschweigend [mm] $\log$ [/mm] zur Basis 2 vorausgesetzt. Und Du solltest vielleicht noch erwähnen, daß Dein $c$ zwischen 0 und 1 liegt, denn dies gehört ebenfalls zur zweiten Bedingung.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:38 Mi 16.01.2013 | | Autor: | bandchef |
> Vergleiche die Behauptung der Aufgabe mit den Folgerungen jedes der drei Fälle. Da paßt nur der dritte.
Und nochmal die gleiche Frage: Wie erkennt man so ad hoc und nur beim blanken ansehen der Rekursionsgleichung, dass "nur" der dritte Falle passen "kann"? Oder ist das einfach die "Hoffnung" dass doch optimistischerweise nur der 3. Fall passen kann? Oder wie muss ich mir das vorstellen?
> Das mit dem Vernachlässigen ist mir zu schwammig. Dies mag für die O-Notation gelten, aber hier haben wir die [mm] $\Omega$-Notation. [/mm] Und dieses "Vernachlässigen" gilt bestimmt nicht für jedes Landau-Symbol.
Das heißt also, dass diese Grenzwertbildung mir dann auch das Problem löst, dass ich hier gestern noch zusätzlich (aus Unwissenheit) gefragt hatte. Ich muss also in Wikipedia oder einer Formelsammlung nachschaun, welcher limes zu welchem Landausymbol gehört und wende diesen dann einfach "stur" an. Wenn nun der limes die mathematische Definition erfüllt, hab ich dann auch sofort geklärt, ob nun die Funktion f in dem jeweiligen (Teil?)-Kalkül (kann man das so sagen?) liegt. Richtig?
> Ja! Hier hast Du wohl stillschweigend zur Basis 2 vorausgesetzt. Und Du solltest vielleicht noch erwähnen, daß Dein zwischen 0 und 1 liegt, denn dies gehört ebenfalls zur zweiten Bedingung.
Naja, ich hab stillschweigen die Basis 2 vorausgesetzt, weil ich mir nicht sicher ob ich hier nun die Basis 2 verwenden darf oder nicht. Das ist einfach dass dumme wenn in Vorlesungsunterlagen stillschweigend einfach $log(n) = [mm] log_2(n)$ [/mm] angewendet wird. Eigentlich müsste man die Basis ja immer angeben! Sicher kann man sich ja dann aber dennoch nie sein :-(
PS: Ich werde heute noch ein oder zwei Aufgabe zu diesem Master-Theorem reinstellen. Wenn du Lust hast, könntest du dir die Aufgabe ja einfach mal anschaun?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:45 Mi 16.01.2013 | | Autor: | Helbig |
Hallo bandchef,
> > Vergleiche die Behauptung der Aufgabe mit den Folgerungen
> jedes der drei Fälle. Da paßt nur der dritte.
>
> Und nochmal die gleiche Frage: Wie erkennt man so ad hoc
> und nur beim blanken ansehen der Rekursionsgleichung, dass
> "nur" der dritte Falle passen "kann"? Oder ist das einfach
> die "Hoffnung" dass doch optimistischerweise nur der 3.
> Fall passen kann? Oder wie muss ich mir das vorstellen?
Du liest in meine Antwort mehr hinein, als ich geschrieben habe. Mit bloßem Anschauen der "Rekursionsgleichung" kann man nicht herausbekommen, welcher der drei Fälle in Frage kommt. Aber laut Aufgabe solltest Du [mm] $T(n)\in\Theta(n\log [/mm] n)$ zeigen, und diese Aussage liefert nur der dritte Fall. Nur deshalb kannst Du für diese Aufgabe die beiden anderen Fälle ignorieren.
>
>
>
>
> > Das mit dem Vernachlässigen ist mir zu schwammig. Dies mag
> für die O-Notation gelten, aber hier haben wir die
> [mm]\Omega[/mm]-Notation. Und dieses "Vernachlässigen" gilt
> bestimmt nicht für jedes Landau-Symbol.
>
> Das heißt also, dass diese Grenzwertbildung mir dann auch
> das Problem löst, dass ich
> hier gestern noch
> zusätzlich (aus Unwissenheit) gefragt hatte. Ich muss also
> in Wikipedia oder einer Formelsammlung nachschaun, welcher
> limes zu welchem Landausymbol gehört und wende diesen dann
> einfach "stur" an. Wenn nun der limes die mathematische
> Definition erfüllt, hab ich dann auch sofort geklärt, ob
> nun die Funktion f in dem jeweiligen (Teil?)-Kalkül (kann
> man das so sagen?) liegt. Richtig?
Richtig. Mit den Landau-Symbolen drückt man gewissen Grenzwertaussagen kurz und knapp aus. Nicht mehr und nicht weniger. Hier im Forum habe ich vor allem gelernt, daß sie mehr schaden als nützen.
> > Ja! Hier hast Du wohl stillschweigend log zur Basis 2
> > vorausgesetzt. Und Du solltest vielleicht noch erwähnen,
> > daß Dein c zwischen 0 und 1 liegt, denn dies gehört
> > ebenfalls zur zweiten Bedingung.
>
> Naja, ich hab stillschweigen die Basis 2 vorausgesetzt,
> weil ich mir nicht sicher ob ich hier nun die Basis 2
> verwenden darf oder nicht. Das ist einfach dass dumme wenn
> in Vorlesungsunterlagen stillschweigend einfach [mm]log(n) = log_2(n)[/mm]
> angewendet wird. Eigentlich müsste man die Basis ja immer
> angeben! Sicher kann man sich ja dann aber dennoch nie sein
> :-(
Doch, da kann man sich sicher sein, wenn man berücksichtigt, daß die gewählte Basis hier irrelevant ist, bzw. daß man die Basis frei wählen kann. Bekanntlich unterscheiden sich Logarithmen zu verschiedenen Basen nur durch einen konstanten Faktor.
Grüße,
Wolfgang
|
|
|
|
