3.1/2 Algowiki und Schlussfolgerungen

Ben Kohr
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 14. Apr 2015 17:41

3.1/2 Algowiki und Schlussfolgerungen

Beitrag von Ben Kohr »

Hallo,

drei Fragen bezüglich der Algowikiseite "Asymptotic comparison of functions" (http://wiki.algo.informatik.tu-darmstad ... _functions) ergaben sich:

1. Sollte bei "Mathematical rules for asymptotic comparsion", Punkt 5, das "Kreis-mit-X-Zeichen" nicht eher durch ein Theta ersetzt werden?
2. Falls ja, sollte dann nicht eigentlich dieser Grenzwert existieren, endlich sein und NICHT 0 sein (sonst -> siehe Punkt 6).
3. Wäre diese Aussage dann gleichbedeutend zu: "Der Limes (ohne "superior") ist existent und nicht 0"?

Viele Grüße
Ben

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: 3.1/2 Algowiki und Schlussfolgerungen

Beitrag von Prof. Karsten Weihe »

Ben Kohr hat geschrieben: 1. Sollte bei "Mathematical rules for asymptotic comparsion", Punkt 5, das "Kreis-mit-X-Zeichen" nicht eher durch ein Theta ersetzt werden?
Nein, durch ein \(\mathcal{O}\); ist korrigiert. :oops:

Ihre Fragen #2 und #3 haben sich nach meinem Verständnis miterledigt :?:

KW

Ben Kohr
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 14. Apr 2015 17:41

Re: 3.1/2 Algowiki und Schlussfolgerungen

Beitrag von Ben Kohr »

Hallo nochmal,

danke für die Antwort! Ich reiche noch eine andere thematisch passende Frage hinterher.

Auf ebendieser Wikiseite findet sich auch (Punkt 5 und 6):
5) It is "f element of O(g))" if, and only if, the [limit superior] of the series f(n)/g(n) for "n to infinity" is finite.
6) It is "f element of o(g))" if, and only if, this limit superior is zero. Note that, due to nonnegativity, this is equivalent to the statement that "lim f(n)/g(n)" exists and equals zero.

Gibt es für den Punkt 5 ebenfalls eine zum Punkt 6 ähnliche Implikation/Biimplikation, wodurch man vom Limes einer Folge f(n)/g(n) auf dessen Limes Superior schließen kann (u.u.)?

Viele Grüße
Ben

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: 3.1/2 Algowiki und Schlussfolgerungen

Beitrag von Prof. Karsten Weihe »

Ben Kohr hat geschrieben: Gibt es für den Punkt 5 ebenfalls eine zum Punkt 6 ähnliche Implikation/Biimplikation, wodurch man vom Limes einer Folge f(n)/g(n) auf dessen Limes Superior schließen kann (u.u.)?
Nur die Implikation, keine Äquivalenz: Wenn der Limes existiert, dann sind Limes Superior und Limes Inferior gleich dem Limes. Also: Wenn der Limes existiert und endlich ist, dann gilt \(f\in\mathcal{O}(g)\). Aus der Äquivalenz von \(f\in o(g)\) und Limes gleich 0 ergibt sich zudem im Falle, dass der Limes existiert und endlich ist: \(f\in\Theta(g)\) genau dann, wenn der Limes nicht 0 ist.

Mehr wüsste ich nicht.

KW

Ben Kohr
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 14. Apr 2015 17:41

Re: 3.1/2 Algowiki und Schlussfolgerungen

Beitrag von Ben Kohr »

Vielen Dank für die Antwort!

Antworten

Zurück zu „Archiv“