Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Komplexitätstheorie, O-Notation

Komplexitätstheorie, O-Notation

Universität / Fachhochschule

Sonstiges

Tags: Sonstig, Theoretische Informatik

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
jonnel

jonnel aktiv_icon

10:59 Uhr, 03.11.2016

Antworten
Hallo,

im Rahmen einer Vorlesung "Theoretische Informatik" soll ich zeigen, dass die Definition der O-Notation:

O(f)={g:ℕk→ℕ ∣ ∃c>0,∃n0∈ℕk ∀n≥n0:g(n)≤c⋅f(n)}

auch äquivalent definiert werden kann, ohne ein wählbares n0 benutzen zu müssen. Stattdessen sollte die einzige Beschränkung für n sein, dass n>0.

Nun sagt die obige Definition meines Erachtens aus, dass mit O(f) die Menge aller Funktionen g bezeichnet wird, die, unter Vernachlässigung eines konstanten Faktors c, höchstens so schnell wachsen wie f, durch diese Funktion also asymptotisch begrenzt werden. n0 ist wählbar, um das Verhalten für große n, also im Grenzwert, hervorzuheben.

Wenn die einzige Beschränkung für n0 ist, dass n0>0, wird aber auch das Verhalten für kleine n berücksichtigt. Die Definitionen wären also nicht mehr äquivalent.

Was übersehe ich?

Vielen Dank im Voraus!

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."
Online-Nachhilfe in Mathematik
Antwort
DerDepp

DerDepp aktiv_icon

11:07 Uhr, 04.11.2016

Antworten
Hossa :-)

Ich kenne und verwende häufig den Grenzwert als äquvalente Definition:

f=O(g)⇔limn→∞f(n)g(n)<∞

Natürlich muss darin n>0 sein, weil der Grenzwert gegen +∞ bestimmt werden muss. Eine Definition nur mit der Forderung n>0 kenne ich nicht und kann es meiner Ansicht nach auch nicht geben. Die O-Notation beschreibt das asymptotische Verhalten einer Funktion f(n). Die Forderung "asymptotisch" (bzw. für große n) muss ja irgendwo in der Definition auftauchen. Oben z.B. steckt sie im Grenzwert.
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.