Groß-Oh-Notation

01.09.2012, 16:39

Fealy

Groß-Oh-Notation

Hi.

Ich hoffe das passt am besten hierhin.

Und zwar habe ich so meine Schwierigkeiten mit der Groß-Oh-Notation.

Wir haben diese in der Vorlesung wie folgt definiert:

g(n) <= c*f(n)

Jetzt haben wir auf einem Übungsblatt eine Tabelle gegeben, und sollen ankreuzen, in welchen Mengen die Funktionen jeweils liegen (ohne Begründung).

Bei einer Funktion jedoch, verstehe ich die Lösung nicht. Generell habe ich mir gemerkt, dass ein Polynom k-ten Grades die asymptotische Laufzeit O(n^k) besitzt.

Die Funktion lautet:

$\begin{eqnarray*} \frac{n^{2}} {log(n+5)} \end{eqnarray*}$

Laut Lösung liegt Funktion in O(n²,2^n,5^n)

Wenn ich allerdings folgendes Anwende:

$\begin{eqnarray*} \frac{n^{2}}{log(n+5)} <= c*n² \end{eqnarray*}$ | teilen durch n²

Ergibt:

$\begin{eqnarray*} \frac{1}{log(n+5)} <= c \end{eqnarray*}$

Also ist die Bedingung für n² doch garnicht erfüllt? Was übersehe ich?

Generell: Wenn ich einen Bruch habe (wie diesen hier), wie kann ich ganz generell darauf schließen, in welcher Menge die Funktion liegt?

Anscheinend kann man dieses "Rezept" für Brüche nämlich nicht anwenden?

Ich freue mich auf Eure Antworten

Lg,
Fealy

01.09.2012, 17:23

weisbrot

Auf diesen Beitrag antworten »

RE: Groß-Oh-Notation
ich verstehe leider nicht ganz wo du das problem siehst.. 1/log(n+5) ist doch nullfolge, und liegt somit in O(1) - das ist genau worauf du durch das kürzen geschlossen hast. lg

01.09.2012, 17:39

Fealy

Auf diesen Beitrag antworten »

Heisst also, dass die Bedingung

g(n) <= c *f(n) erfüllt ist, da mit steigendem N 1/log(n+5) gegen Null geht, und c was weiß ich für ne Konstante sein kann?

In meiner Lösung stehen die folgenden Mengen zum Ankreuzen:

0(1), O(log*n), O(n), O(n*log*n), O(n²), O(2^n), O(5^n).

Für die Funktion ist in der Musterlösung aber nur die letzten 3 angekreuzt (Von rechts nach links).

Wie genau schliesst du auf O(1)? Ich habe doch lediglich die Überprüfung für O(n²) gemacht?

Ansonsten bleibt mir immernoch die Frage offen: Wie schließe ich (vor allem bei Brüchen) nur aus reinem Überlegen auf die zutreffenden Mengen für eine gegebene Funktion?

Lg,
Fealy

01.09.2012, 17:45

Airblader

Auf diesen Beitrag antworten »

RE: Groß-Oh-Notation

Zitat:

Original von Fealy
Wir haben diese in der Vorlesung wie folgt definiert:

g(n) <= c*f(n)

Entweder, du gibst uns hier eure Definition gnadenlos falsch wieder oder eure Vorlesung ist unbrauchbar -- ich tippe aus Erfahrung auf Ersteres. Aber das ist weder die korrekte, noch irgendeine Definition.

Aus den Beiträgen kann man schließen, dass dir jegliches Verständnis bezüglich der Landau-Symbolik fehlt. Und genau darum ist das Bearbeiten von Aufgaben im Moment aus meiner Sicht zwecklos. Du solltest dir zunächst nochmal die (korrekte!) Definition ansehen und vor allem verstehen, bevor du Aufgaben löst.

Beispiele helfen beim Verständnis -- aber nur solche mit Lösungsweg. Ich rate jetzt einfach mal, dass du Informatik studierst bzw. das eine Informatikvorlesung ist. In diesem Fall findest du im Internet genügend solcher Beispiele (Stichwort asymptotische Laufzeit).

Edit: weisbrots Antwort ist übrigens lediglich missverständlich. 1/log(n+5) ist zwar in O(1), aber n²/log(n+5) nicht.

air

01.09.2012, 18:03

Airblader

Auf diesen Beitrag antworten »

Um noch kurz zu verdeutlichen, was weisbrot wohl gemeint hatte:

$\begin{eqnarray*} n^2 \in \mathcal O(n^2) \end{eqnarray*}$ sollte klar sein. Weiß man zudem $\begin{eqnarray*} \frac{1}{\log(n+5)} \in \mathcal O(1) \end{eqnarray*}$ , dann folgt mit den "Rechenregeln" auch $\begin{eqnarray*} n^2 \cdot \frac{1}{\log(n+5)} \in \mathcal O(n^2 \cdot 1) \end{eqnarray*}$ .
Die anderen beiden Aussagen folgen damit mehr oder weniger direkt auch -- aber wie gesagt, zunächst mal solltest du verstehen, was die Notation überhaupt bedeutet. Alles eben Gesagte setzt natürlich voraus, dass ihr solche Rechenregeln schon kennt. Andernfalls muss man eben elementar über die Definition argumentieren (auch nicht viel schwieriger).

Noch eine Kleinigkeit: Es heißt nicht $\begin{eqnarray*} \log \cdot n \end{eqnarray*}$ -- was sollte das denn auch sein? Der Logarithmus ist eine Funktion, also $\begin{eqnarray*} \log n = \log(n) \end{eqnarray*}$ , das Argument ohne Klammern zu schreiben ist lediglich eine Konvention, um etwas faul sein zu dürfen. Der Malpunkt ist jedoch schlicht falsch.

air

01.09.2012, 18:11

Fealy

Auf diesen Beitrag antworten »

Hey:

Hier die genaue Definition der Groß-Oh-Notation

O(f) = {g | ∃ c1,c2 > 0 ∃ n0 ∈ N : ∀n ≥ n0 : g(n) ≤ c1 * f(n) + c2}

(Das ist doch im Grunde genau das, was ich geschrieben habe, oder?). Bin kein Informatikstudent, sondern habe das Fach nur als 20%iges Nebenfach. Daher sind auch meine mathematischen Kenntnisse dementsprechend sehr beschränkt.

Wenn also g Element O(f) ist, so wächst g also asymptotisch (für große N?) nicht schneller als f (deswegen doch auch das <= ?).

Bin mir schon sicher, dass das so zu verstehen ist?

Ich muss doch einfach ein c finden, für welches die Bedingung erfüllt wird. Ist dies gegeben dann liegt eine funktion g(n) in f(n) - oder?

Wenn ihr mir Anhaltspunkte geben würdet, wo mein Verständnisfehler liegt, werde ich gerne Versuchen diesen auszumerzen. Drehe mich hier alleiner aber leider auf der Stelle.

Wir haben genau 2 Aufgaben dazu gemacht.

Bei der einen hat man 5 Funktionen gegeben und soll (ohne Begründung) ankreuzen in welchem Mengen (vgl.) oben diese liegen.

Hier habe ich wie gesagt Probleme, wenns um Brüche geht?

Bei der 2 Aufgabe haben wir bspw. gegeben:

Zeigen oder widerlegen Sie:

2n = O(n)

Ich gehe also einfach hin (so haben wirs in der Übung gemacht):

2n <= c * n | Ich teile durch n

2 <= c | Für c = 2 bspw. erfüllt. => Wahre Aussage.

Wo ist Anzusetzen?

Lg,

01.09.2012, 18:20

Airblader

Auf diesen Beitrag antworten »

Zitat:

Original von Fealy
Hier die genaue Definition der Groß-Oh-Notation

O(f) = {g | ∃ c1,c2 > 0 ∃ n0 ∈ N : ∀n ≥ n0 : g(n) ≤ c1 * f(n) + c2}

Es gibt den Vorschau-Button aus gutem Grund -- dann passieren solche Copy&Paste-Fehler nicht. Glücklicherweise ist mir die Definition auch so geläufig, du brauchst sie nicht zu wiederholen. Mir liegt aber daran, dass du verstehst, dass

Zitat:

(Das ist doch im Grunde genau das, was ich geschrieben habe, oder?)

eben nicht der Fall ist. Was du geschrieben hast war ein aus dem Zusammenhang gerissener Formelfetzen. Mit der Definition hat dies nichts zu tun, und wer Landausymbole vorher nicht schon kennt, der hätte mit deiner "Definition" im ersten Beitrag nichts anfangen können. Augenzwinkern

Zitat:

Bin kein Informatikstudent, sondern habe das Fach nur als 20%iges Nebenfach. Daher sind auch meine mathematischen Kenntnisse dementsprechend sehr beschränkt.

Was studierst du denn?

Zitat:

Wenn also g Element O(f) ist, so wächst g also asymptotisch (für große N?) nicht schneller als f (deswegen doch auch das <= ?).

Richtig, sozusagen. Etwas genauer bedeutet es eben, dass g bis auf eine Konstante durch f beschränkt ist.

Zitat:

Ich muss doch einfach ein c finden, für welches die Bedingung erfüllt wird. Ist dies gegeben dann liegt eine funktion g(n) in f(n) - oder?

Korrekt. Wichtig ist, dass du ein c findest, so dass die Bedingung für alle n erfüllt ist.

Zitat:

Zeigen oder widerlegen Sie: 2n = O(n)

Ich gehe also einfach hin (so haben wirs in der Übung gemacht):
2n <= c * n | Ich teile durch n
2 <= c | Für c = 2 bspw. erfüllt. => Wahre Aussage.

Korrekt. Und das selbe machen wir nun für deine Funktion. Du hattest ja bereits zu

$\begin{eqnarray*} \frac{1}{\log(n+5)} \leq c \end{eqnarray*}$

umgeformt. Jetzt sehen wir, dass die Folge links eine monoton fallende Folge ist. Monoton fallende Folgen sind durch ihr erstes Folgenglied beschränkt, es gilt also $\begin{eqnarray*} \frac{1}{\log(n+5)} \leq \frac{1}{\log 5} \end{eqnarray*}$ . Wählen wir eben jene Zahl als unser c, so ist die obige Ungleichung also erfüllt -- und damit $\begin{eqnarray*} \frac{n^2}{\log(n+5)} \in \mathcal O(n^2) \end{eqnarray*}$ .

air

01.09.2012, 18:43

Fealy

Auf diesen Beitrag antworten »

Okay gut. Dann war mein Verständnis ja gar nicht soooooo verkehrt. Ich studiere BWL mit Informatik (20%) an einer TU. Bin in den Info-Sachen eigentlich recht gut, wobei ich quantitativ eher schlecht aufgestellt bin (Lücken über Lücken).

Damit ihr vielleicht eher eine Ahnung habt, wie die eine Aufgabe aussieht, habe ich diese mal abfotografiert:

https://dl.dropbox.com/u/12234165/DSC00114.jpg

So eine Aufgabe wird wohl (aller Voraussicht nach) auch in der anstehenden Klausur drankommen.

Wenn ich dies also explizit ohne Begründung machen soll. Dann ist es für mich immernoch ein Problem, wenn ich Brüche habe. Ich muss doch dann irgendwie darauf schließen können, worin f3 liegt (Ich hab dann ja pro Funktion wohl nur 1 Minute Zeit)

Wenn ich den Test für O(1) mache (und jetzt bitte steinigt mich nicht, wenn ich jetzt hier Bullshit verzapfe), komme ich allerdings auf folgendes.

$\begin{eqnarray*} \frac{n²}{log(n+5)} \leq c*1 \end{eqnarray*}$
<=>

$\begin{eqnarray*} \frac{n²}{log(n+5)} \leq c \end{eqnarray*}$

Ich kann daraus doch schließen, dass der Linke Term nach Unendlich strebt, da n² Stärker wächst wie log(n+5). Wenn ich das jetzt richtig verstanden habe, muss ich doch daraus schließen, dass kein c zu finden ist, so dass die Bedingung für alle n erfüllt ist.

Lg,
Fealy

01.09.2012, 18:58

Airblader

Auf diesen Beitrag antworten »

Bis auf eine sprachliche Ungenauigkeit (2*n wächst auch stärker als n, der Quotient divergiert dennoch nicht) ist das korrekt und es gilt in der Tat $\begin{eqnarray*} \frac{n^2}{\log(n+5)} \notin \mathcal O(1) \end{eqnarray*}$ .

Ob die Funktion ein Bruch ist oder nicht spielt erstmal keine Rolle -- es bleibt ja die selbe Aufgabenstellung und Definition. Wenn es darum geht, das Ganze nun "schnell" zu sehen: Übung!

Wer geübt ist, sieht sofort, dass der Nenner das n² nur kleiner macht. Etwas mehr in Formeln ausgedrückt:
$\begin{eqnarray*} \frac{n^2}{\log(n+5)} \leq \frac{n^2}{1} = n^2 \leq 1 \cdot n^2 =: c \cdot n^2 \end{eqnarray*}$
Damit ist sofort klar, dass die Funktion in $\begin{eqnarray*} \mathcal O(n^2) \end{eqnarray*}$ liegt, also in einer polynomialen Klasse. Damit liegt sie aber auch direkt in den exponentiellen Klassen $\begin{eqnarray*} \mathcal O(2^n) \end{eqnarray*}$ und $\begin{eqnarray*} \mathcal O(5^n) \end{eqnarray*}$ (*).
Jetzt muss man noch verstehen, warum sie nicht in den anderen Klassen liegt. Dass die Folge divergiert lässt sich zum Beispiel direkt sehen (hast du ja auch). Damit ist $\begin{eqnarray*} \mathcal O(1) \end{eqnarray*}$ schonmal raus. Bei den übrigen Klassen würden wir beim "Rüberteilen-Schritt" zwar bis zu ein 'n' bekommen, das wir kürzen könnten, aber selbst die dazukommenden Logarithmen im Nenner gleichen nicht das Wachstum des verbleibenden linearen Zählerterms aus (den Satz bitte mehrfach lesen und nebenbei mit diesen Klassen mal durchrechnen, dann verstehst du, was ich meine).

Wie gesagt: So kann man sowas ganz schnell sehen. Aber das erfordert eben ein wenig Übung.

(*) Ein Faktum, das du dir am Besten gleich jetzt mal klar machst, indem du z.B. beweist, dass $\begin{eqnarray*} f \in \mathcal O(n^2) \Rightarrow f \in \mathcal O(2^n) \end{eqnarray*}$ gilt. Dazu genügt es, dass du $\begin{eqnarray*} n^2 \in \mathcal O(2^n) \end{eqnarray*}$ zeigst (wobei du verstehen solltest, wieso das ausreicht).

air
P.S.: Bilder bitte nicht auf externen Plattformen hochladen, sondern direkt hier im Board (beim Schreiben des Beitrages findest du direkt unter dem Textfeld einen Button "Dateianhänge").

01.09.2012, 19:32

Fealy

Auf diesen Beitrag antworten »

Hey,

vorab möchte ich mich nochmal für deine Mühe und Hilfe bedanken.

Wenn eine Funktion A asymptotisch nicht schneller wächst als eine Funktion B, Dann ist mir durchaus klar, dass A nicht schneller wachsen kann als C wenn gilt, dass: C asymptotisch schneller wächst als B.

Zu deiner Aufgabe:

$\begin{eqnarray*} n²\leq c * 2^{n} \end{eqnarray*}$ | ln ()

$\begin{eqnarray*} 2ln(n) \leq c * n*ln(2) \end{eqnarray*}$ | c=2

$\begin{eqnarray*} 2ln(n) \leq 2n * ln(2) \end{eqnarray*}$

Somit ist die Bedingung erfüllt.

Lg,
Fealy

01.09.2012, 20:06

Airblader

Auf diesen Beitrag antworten »

Du hast das Logarithmengesetz falsch angewendet. Da müsste stehen

$\begin{eqnarray*} 2 \ln n \leq n \cdot \ln 2 + \tilde{c} \end{eqnarray*}$

mit $\begin{eqnarray*} \tilde{c} := \ln c \end{eqnarray*}$ , aus der multiplikativen wurde also eine additive Konstante. Wieso das jetzt unmittelbar gelten soll sehe ich nicht.

Typischerweise macht man es ein wenig anders. Wir wollen ja

$\begin{eqnarray*} n^2 \leq c \cdot 2^n \end{eqnarray*}$

zeigen. Nun gilt $\begin{eqnarray*} (2^n)' = \ln(2) \cdot 2^n = \underbrace{2\ln(2)}_{> 1} \cdot 2 \cdot 2^{n-2} \geq 2n = (n^2)' \end{eqnarray*}$ für $\begin{eqnarray*} n \geq 4 \end{eqnarray*}$ und $\begin{eqnarray*} 4^2 = 16 \leq 16 = 2^4 \end{eqnarray*}$ , für $\begin{eqnarray*} n \geq 4 \end{eqnarray*}$ ist obige Ungleichung also erfüllt, da die Ungleichung für $\begin{eqnarray*} n=4 \end{eqnarray*}$ erfüllt ist und die rechte Seite stets schneller wächst.
Den Fall $\begin{eqnarray*} n < 4 \end{eqnarray*}$ können wir getrost ignorieren -- das sind nämlich nur endlich viele Zahlen, die wir durch entsprechende Wahl der Konstanten $\begin{eqnarray*} c \end{eqnarray*}$ mühelos unter Kontrolle bekommen.

Bei deiner Aufgabe sind alle Klassen übrigens von links nach rechts geordnet, d. h. wenn in einer Spalte ein Kreuz gesetzt werden muss, dann auch in allen Spalten rechts davon. Andersrum, wird in einer Spalte kein Kreuz gesetzt, dann auch in keiner Spalte links davon. Das ist natürlich nicht bei jeder Aufgabe so.
Im Grunde haben wir das ja eben gezeigt, um eben zu nutzen: Liegt es in O(n^2), dann auch in O(2^n) und O(5^n). Analog, da es nicht in O(n*log n) liegt, liegt es z. B. auch nicht in O(1). Ist man sich über diese Inklusionen der Klassen bewusst, muss man gar nicht alle Fälle einzeln durchgehen.

air

Neue Frage »

Antworten »

Groß-Oh-Notation

Verwandte Themen