Beweisen bei Algorithmen < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:52 Di 22.04.2014 | | Autor: | Max80 |
| Aufgabe | [mm]n^2 - 7n +5 = \Theta(n log n)[/mm]<br>
Beweisen oder widerlegen Sie! |
<br>
Hallo zusammen,
ich dachte eigentlich, ich hätte das Thema verstanden. Aber offesichtlich doch nicht. Das Thema sind Algorithmen und da geht es darum, dass man die Laufzeit berechnen kann und dass es dabei abhängige Größen gibt wie die Probleminstanz (Eingabewerte). Leider verstehe ich jetzt nur noch Bahnhof. Wie soll ich das obige denn nun beweisen? Unser Skript kann man ganz klar vergessen. Meine Frage wäre also, ob man anhang eines Beispiels das Prinzip hier vielleicht erklären kann, oder ob ich mir das irgendwie anders erarbeiten kann? Vielen Dank!! Gruß Max
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:59 Di 22.04.2014 | | Autor: | fred97 |
> [mm]n^2 - 7n +5 = \Theta(n log n)[/mm]<br>
> Beweisen oder
> widerlegen Sie!
>
> <br>
>
> Hallo zusammen,
>
> ich dachte eigentlich, ich hätte das Thema verstanden.
> Aber offesichtlich doch nicht. Das Thema sind Algorithmen
> und da geht es darum, dass man die Laufzeit berechnen kann
> und dass es dabei abhängige Größen gibt wie die
> Probleminstanz (Eingabewerte). Leider verstehe ich jetzt
> nur noch Bahnhof. Wie soll ich das obige denn nun beweisen?
> Unser Skript kann man ganz klar vergessen. Meine Frage
> wäre also, ob man anhang eines Beispiels das Prinzip hier
> vielleicht erklären kann, oder ob ich mir das irgendwie
> anders erarbeiten kann? Vielen Dank!! Gruß Max
$ [mm] n^2 [/mm] - 7n +5 = [mm] \Theta(n [/mm] log n) $ bedeutet:
es gibt a,b > 0 und N [mm] \in \IN [/mm] mit
$ a(n*logn) [mm] \le n^2-7n+5 \le [/mm] b(n*logn)$ für n>N.
Hilft das ?
FRED
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:02 Di 22.04.2014 | | Autor: | Max80 |
<br>
Hi,
danke für die Antwort. Wenn ich ehrlich bin verstehe ich nur Bahnhof. Woher kommen denn jetzt a und b?
Woher weißt du, dass N nur natürliche Zahlen sein können? Ist das immer so? Bei den Sortierfällen in der Uni sicherlich häufiger (oder fast immer)
der Fall, aber woher weißt du das hier bei dieser speziellen Formel?
Die letzte Zeile verstehe ich leider gar nicht. :(
Wie kommst du auch diese Zeile? Danke!!!!
Viele Grüße
Max
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:37 Di 22.04.2014 | | Autor: | fred97 |
> <br>
>
>
> <br>
> Hi,
> danke für die Antwort. Wenn ich ehrlich bin verstehe ich
> nur Bahnhof. Woher kommen denn jetzt a und b?
> Woher weißt du, dass N nur natürliche Zahlen sein
> können? Ist das immer so? Bei den Sortierfällen in der
> Uni sicherlich häufiger (oder fast immer)
> der Fall, aber woher weißt du das hier bei dieser
> speziellen Formel?
> Die letzte Zeile verstehe ich leider gar nicht. :(
> Wie kommst du auch diese Zeile? Danke!!!!
Wie wurde bei Euch denn [mm] \Theta [/mm] definiert ?!
FRED
>
> Viele Grüße
> Max
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:46 So 27.04.2014 | | Autor: | Max80 |
<br>
Hallo Fred,
also so langsam bin ich schlauer geworden, aber lösen kann ich das immer noch nicht. Also das Zeichen (ich kenne den Namen nicht): [mm] \Theta[/mm] besagt die "genaue Wachstumsrate". Also nicht obere oder untere Schranke. Mir ist also klar, dass ich beweisen soll, dass die Funktion der Wachstumsrate von O(nlogn) entspricht. Mir ist aber nicht dein Ansatz mit den zwei Konstanten jetzt klar.
Vielen Dank!
Gruß
Max
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:55 Mo 28.04.2014 | | Autor: | Teufel |
Hi!
Das Ding ist ein großes Theta. Es gilt [mm] $f=\Theta(g)\gdw f=\mathcal{O}(g)\cap \Omega [/mm] (g)$.
Ferner gilt [mm] $f=\mathcal{O}(g)\gdw \exists [/mm] c>0, N: [mm] f(n)\le [/mm] cg(n) [mm] \forall [/mm] n>N$. Wenn dir das zu unhandlich ist, kannst du auch folgende Äquivalenz nutzen:
[mm] $f=\mathcal{O}(g)\gdw \limsup\limits_{n \to \infty}\frac{f(n)}{g(n)}<\infty$.
[/mm]
Analog gilt
[mm] $f=\Omega(g)\gdw \liminf\limits_{n \to \infty}\frac{f(n)}{g(n)}>0$.
[/mm]
Versuch das jetzt mal auf deine Aufgabe anzuwenden.
|
|
|
|
