0 Daumen
922 Aufrufe

Aufgabe: O-Notation

f(n)=100n+log(n),g(n)=n+(log(n))2f(n) = 100\cdot n + \log(n),\quad g(n) = n + (\log(n))^2


Problem/Ansatz:

Hallo könnt mir jemand diese Aufgabe vormachen :D ? Ich kapier das Thema null wäre sehr nett :).

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

Hallo :-)

sollst du auf fO(g)f\in \mathcal{O}(g) oder gO(f)g\in \mathcal{O}(f) untersuchen?

Avatar von 15 k

das erste :D

Wie hast du denn die Definition zur O-Notation kennengelernt?

ja der prof hat dazu nicht viel gesagt und ich hatte das in mathe 1 nicht und brauche es für ein anderes fach :) ich weiß nur dass es für algorithmen benutzt wird um die effizienz zu messen.

ich habs versucht wie ein grenzwert zu rechnen bin aber nicht weitergekommen also mit n -> inf

also hab bis jetzt lim n->inf (100 + logn/n)/(1+ (logn)2/n))

Das mit dem Limes so zu machen gibt es nur bei der klein O-Natation (o\mathcal{o}). Die kannst du aber auch benutzen, denn wenn fo(g)f\in \mathcal{o} (g) gilt, dann gilt auch fO(g)f\in \mathcal{O}(g).

Für fo(g)f\in \mathcal{o} (g) musst du limnf(n)g(n)=0\lim\limits_{n\to \infty}\frac{f(n)}{g(n)} =0 zeigen.

Dann hast du

f(n)g(n)=100n+log(n)n+(log(n))2=100+log(n)n1+(log(n))2nn1000\frac{f(n)}{g(n)} = \frac{100\cdot n + \log(n)}{n + (\log(n))^2}=\frac{100+\frac{\log(n)}{n}}{1+\frac{(\log(n))^2}{n}}\quad \stackrel{n\to \infty}{\longrightarrow }\quad 100\neq 0

Damit gilt schonmal nicht fo(g)f\in \mathcal{o} (g).

Bleibt nun die Groß O-Notation.

Dafür gilt diese Definition:

Es sei g : NRg: \mathbb{N}\rightarrow \mathbb{R}. Dann istO(g) : ={f :  NR :  α>0 n0N nn0 :  0f(n)αg(n)0f(n) f(n)αg(n)} \mathcal{O}(g):=\{f:\ \mathbb{N}\rightarrow \mathbb{R}:\ \exists \alpha>0 \ \exists n_0 \in \mathbb{N} \ \forall n\geq n_0:\ \underbrace{0\leq f(n) \leq \alpha \cdot g(n)}_{0\leq f(n) \ \land f(n)\leq \alpha\cdot g(n) } \}

Für fO(g)f\in \mathcal{O} (g) musst du per Definition eine Konstante α>0\alpha>0 und eine Stelle n0Nn_0 \in \mathbb{N} angeben, sodass für alle nn0n\geq n_0 die Ungleichung 0f(n)αg(n)0\leq f(n) \leq \alpha \cdot g(n) gilt. Entweder sieht man sofort, wie beide Parameter gewählt werden müssen oder du probierst erstmal rum. Ich nehme folgende Abschätzungen vor: Welche Basis hier der Logarithmus annimmt ist vom Prinzip egal. Ich nehme hier mal den 10er-Logarithmus.

0<100n1f(n)=100n+log(n)100n+100log(n)n10100n+100log(n)log(n)=100n+100(log(n))2=100(n+(log(n))2)=100g(n)\begin{aligned}0&<100 \stackrel{n\geq 1}{\leq} f(n)\\&=100\cdot n+\log(n)\\&\leq 100\cdot n+100\cdot \log(n)\\&\stackrel{n\geq 10}{\leq}100\cdot n+100\cdot \log(n)\cdot \log(n)\\&=100\cdot n+100\cdot (\log(n))^2\\&=100\cdot (n+(\log(n))^2)=100\cdot g(n)\end{aligned}

Für α=100\alpha=100 und n0=10n_0=10 gilt für alle n10n\geq 10 die Ungleichung

0f(n)αg(n)0\leq f(n)\leq \alpha\cdot g(n), d.h. es gilt fO(g)f\in \mathcal{O}(g).

Vielen Dank für diese ausführliche Antwort :)). Bei dem unteren Teil wieso ist g(n) = log(n) ? wieso heißt es nicht 100 * (n + (logn)2) ? Oder verstehe ich was falsch.

Aber unten steht doch nicht g(n)=log(n)g(n)=\log(n), sondern

100(n+(log(n))2)=100g(n)100\cdot (n+(\log(n))^2)=100\cdot g(n)

ehm ich mein bei <= 100 * n + 100*log(n) wieso kommt da noch eine 100 dazu ?

also noch bei n>=1

Ich habe dort den Term log(n)\log(n) durch 100log(n)100\cdot \log(n) nachoben abgeschätzt.

ah ok danke :).

Sehr gerne. :-)

Hi,

nochmal eine Verständnisfrage für  gO(f)g\in \mathcal{O}(f) würde demnach auch was rauskommen (1/100) ?

Nein. Das funktioniert allgemein nicht so. Was du allerdings sagen kannst ist:

fO(g)(1)gΩ(f)(2)\underbrace{f\in \mathcal{O}(g)}_{(1)}\Leftrightarrow \underbrace{g\in \Omega(f)}_{(2)}

(1) :  f wa¨chst bis auf eine Konstante ho¨chstens so schnell wie g(1): \text{ f wächst bis auf eine Konstante höchstens so schnell wie g}

(2) :  g wa¨chst bis auf eine Konstante mindestens so schnell wie f(2): \text{ g wächst bis auf eine Konstante mindestens so schnell wie f}

gO(f)g\in \mathcal{O}(f) hingegen ist erstmal eine völlig andere Aussage. Dazu musst du also zeigen:

α>0 n0N nn0 :  0g(n)αf(n)\exists \alpha>0 \ \exists n_0 \in \mathbb{N} \ \forall n\geq n_0:\ 0\leq g(n) \leq \alpha \cdot f(n)

Dafür betrachtest zb folgende Abschätzung(en):

0n1g(n)=n+(log(n))2[n+(log(n))2]+log(n)=[n+log(n)]+(log(n))299nn+log(n)+99n=100n+log(n)=f(n)\begin{aligned}0\stackrel{n\geq 1}{\leq}g(n)&=n+(\log(n))^2\\&\leq [n+(\log(n))^2]+\log(n)\\&= [n+\log(n)]+\underbrace{(\log(n))^2}_{\leq 99\cdot n}\\&\leq n+\log(n)+99\cdot n\\&=100\cdot n+\log(n)=f(n) \end{aligned}

Mit α=1\alpha=1 und n0=1n_0=1 folgt also auch gO(f)g\in \mathcal{O}(f).

Ein anderes Problem?

Stell deine Frage