Landausches Ordnungssymbol O

23.08.2017, 21:43

matheamateur61

Landausches Ordnungssymbol O

Meine Frage:
Hallo ich verstehe in meinem Skript das Prinzip vom landauschen Ordnungssymbol überhaupt nicht. Könnte mir jemand das anhand der folgenden Aufgabe erklären?

(3teWurzel)von ((n^2)+1) = (n^(2/3)*(3teWurzel)von (1+(1/n^2) = Landausches Ordnungssymbol O (n^(2/3)

wegen (3teWurzel)von (1+(1/n^2)) Element von [1, (3teWurzel)von 2] .

Meine Ideen:
Ich verstehe, dass das landausche Ordnungssymbol zeigen soll, dass die Folge maximal so wächst, wie O. Wie findet man den bestimmten Wert? Ich verstehe es wirklich gar nicht und deswegen bräuchte ich dringend Hilfe.

24.08.2017, 13:59

HAL 9000

Auf diesen Beitrag antworten »

Ich versuche mal aus dem nahezu unleserlichem Scan sowie dem hier

Zitat:

Original von matheamateur61
(3teWurzel)von ((n^2)+1) = (n^(2/3)*(3teWurzel)von (1+(1/n^2) = Landausches Ordnungssymbol O (n^(2/3)

wegen (3teWurzel)von (1+(1/n^2)) Element von [1, (3teWurzel)von 2] .

was vernünftig lesbares zu machen:

Zitat:

$\begin{align*} \sqrt[3]{n^2+1} = n^{\frac{2}{3}}\cdot \sqrt[3]{1+\frac{1}{n^2}} = \mathcal{O}\left( n^{\frac{2}{3}} \right) \end{align*}$ wegen $\begin{align*} \sqrt[3]{1+\frac{1}{n^2}}\in \left[1, \sqrt[3]{2} \right] \end{align*}$ .

Nun zu deinen Fragen:

Zitat:

Original von matheamateur61
Wie findet man den bestimmten Wert?

Sowas wie den bestimmten Wert gibt es nicht. Man kann unter Einschränkung auf Potenzfunktionen fragen, ob es Exponenten $\begin{align*} \alpha \end{align*}$ mit $\begin{align*} \sqrt[3]{n^2+1} = \mathcal{O}\left( n^{\alpha} \right) \end{align*}$ gibt und falls ja, welche $\begin{align*} \alpha \end{align*}$ das erfüllen.

Dazu muss man begreifen, was $\begin{align*} f(n)=\mathcal{O}(g(n)) \end{align*}$ bedeutet: Streng nach Definition heißt das, dass $\begin{align*} \left| \frac{f(n)}{g(n)} \right| \end{align*}$ für große $\begin{align*} n\geq n_0 \end{align*}$ (aber damit automatisch auch für die nur endlich vielen kleineren $\begin{align*} n \end{align*}$ ) beschränkt bleibt. Im speziellen Fall von $\begin{align*} g(n)=n^{\alpha} \end{align*}$ heißt das also für unser $\begin{align*} f(n)=\sqrt[3]{n^2+1} \end{align*}$ : Durch welche Potenz müssen wir $\begin{align*} f(n) \end{align*}$ teilen, so dass der Quotient für alle $\begin{align*} n \end{align*}$ beschränkt bleibt. Diesem Zweck dient die obige Umformung: In

$\begin{align*} f(n) = n^{\frac{2}{3}}\cdot \sqrt[3]{1+\frac{1}{n^2}} \end{align*}$

bleibt der hintere Faktor beschränkt, genauer gesagt ist wie festgestellt $\begin{align*} \sqrt[3]{1+\frac{1}{n^2}}\in \left[1, \sqrt[3]{2} \right] \end{align*}$ , und das hinten ist ja ein beschränktes Intervall. Damit klappt also die Sache mit $\begin{align*} \alpha=\frac{2}{3} \end{align*}$ . Sie klappt auch mit größeren $\begin{align*} \alpha \end{align*}$ , aber gewöhnlich gibt man den kleinsten möglichen solchen Exponenten an, weil das die schärfste Aussage liefert, in dem Zusammenhang wäre hier auch das diesbezüglich genauere Landau-Symbol $\begin{align*} f(n)=\Theta\left( n^{\frac{2}{3}} \right) \end{align*}$ hier möglich gewesen.

Betrachtet man hingegen kleinere $\begin{align*} \alpha \end{align*}$ , also $\begin{align*} \alpha<\frac{2}{3} \end{align*}$ , so klappt dies nicht: Hier ist dann

$\begin{align*} \lim_{n\to\infty} \frac{f(n)}{n^{\alpha}} = \lim_{n\to\infty} n^{\frac{2}{3}-\alpha}\cdot \sqrt[3]{1+\frac{1}{n^2}} = \infty \end{align*}$ ,

also keine Beschränktheit mehr, und damit auch kein $\begin{align*} f(n)=\mathcal{O}\left(n^{\alpha}\right) \end{align*}$ für diese $\begin{align*} \alpha<\frac{2}{3} \end{align*}$ .

Neue Frage »

Antworten »

Landausches Ordnungssymbol O

Verwandte Themen