Big-Oh Notation

View all featured content
Henrik

Henrik

Dr Franke Ghostwriter
Community,

ich verstehe nicht ganz, wie ich an folgende Aufgabe herangehen soll:
"
Seien
[TEX]f : \mathbb N \math-> \mathbb R \math[/TEX] und [TEX] g : \mathbb N \math -> \mathbb R \math[/tex] Abbildungen mit
[TEX] f (n) := n^{2}
g(n) := n^{4}-80[/TEX]
für alle [TEX] n \in \mathbb N. [/TEX]

Zeigen Sie, dass f = O(g)!"

Kann mir jemand genau erklären wie das gezeigt werden kann?

Danke
Henrik
 
Nach Datum sortieren Nach Stimmen sortieren
ich fand dieses Skript ganz hilfreich:

https://michaelgoerz.net/studies/semester01/comp_sci2/inf_skript.pdf

Es beinhaltet eine Einführung in das Thema und ab Seite 15 werden verschiedene Aufgabentypen zum O-Kalkül besprochen unter anderem auch solche, die in den vergangenen Klausuren abgefragt wurden.

Kurz zusammengefasst: Es muss gezeigt werden, ab welchem n und c die Funktion c*g(n) = c*(n^4 - 80) immer größer oder gleich f(n) = n^2 ist. Das ist hier bei c=1 und n=4 der Fall. Hier lässt sich c und n leicht durch ausprobieren testen und somit bestimmen. Ein Beweis ist das dann natürlich nicht, dürfte aber evtl. auch Punkte bringen.

Bye,
Tomasz
 
Positive Stimme 0 Negative Stimme
Antworten
Oben