Hallo!
Häufiger stoße ich auf die Formulierung "is of order n-1", abgekürzt O(n-1), z.B. wenn es um den "bias" einer Parameterschätzung geht. Außerdem taucht manchmal noch o(n-1), also klein o, auf.
Wer kann mir sowohl mathematisch als auch verbal erklären, was sich hinter dieser Formulierung verbirgt? Auch weiterführende Links würden mir sehr helfen.
Danke.
Gruß,
Oliver Walter
Hallo,
O- bzw. o-Notation dienen dazu, daß asymptotische Verhalten einer Funktion nach oben zu begrenzen. Falls g in O(n-1) ist, besagt das z.B., daß g für beliebig große Werte sich durch die Hyperbel c/x nach oben beschränken läßt. o(n-1) ist strikter und fordert, daß dies selbst für die mit einen beliebigen Faktor c gestreckten c*g gilt. U.a. folgt aus g in o(f), daß für beliebig große Werte der Bruch g(x)/f(x) gegen 0 konvergiert. Das ganze stellt damit eine Abschätzung + Abstraktion von Vorfaktoren dar. Math. lassen sich O(f) bzw. o(f) als Funktionsmengen definieren:
O(f)={ g | ex. c>0, ex x'. fa. x>=x'. g(x)<=c*f(x) }
o(f)={ g | fa. c>0. ex x'. fa. x>=x'. g(x)<=c*f(x) }
verbal: Falls g in O(f) gibt es ein c>0 und einen x' ab dem g(x)<=c*f(x) gilt, bei g in o(f) gibt es zu jedem c>0 ein x' ab dem g(x)<=c*f(x) gilt. Verständlicherweise gilt o(f) => O(f).
Gruss
Enno
Hallo Oliver,
auch wenn Enno das schon vermutlich völlig ausreichend (bzw. sehr gut) erklärt hat, vielleicht eine kleine Ergänzung: Man nennt diese Zeichen auch "Landau-Symbole". Das nur, falls Du nach weiteren Links suchen möchtest.
Einen, der einem relativ schnell entgegenpoppt, ist z.B.:
http://www.wikipedia.org/wiki/Landau_symbol
Viele Grüße,
Martin
Hallo!
Häufiger stoße ich auf die Formulierung "is of order
n-1", abgekürzt O(n-1), z.B. wenn es um
den "bias" einer Parameterschätzung geht. Außerdem taucht
manchmal noch o(n-1), also klein o, auf.
Hallo Enno, hallo Martin!
Ihr habt mir sehr geholfen. Vielen Dank.
Grüße,
Oliver Walter