O Notation n² in n?

[b1zarRe]

Hi,

ich dachte ich hätte die O-Notation nach viel Lernerei begriffen, jedoch erschließt sich für
mich folgendes Beispiel nicht (selbst ausgedacht):

f(n) = n² + 1 -> Man kann hier eigentlich schon sehen, dass die Funktion in O(n²) liegt [sowie
in "oberen" Teilmengen O(n³), (...)]

Frage: f(n) aus O(n)? -> Nein..., aber warum geht dann diese Gleichung bei mir auf?

Zu zeigen:
Exisitert c > 0, Stelle n >= 0 aus Natürlichen Zahlen mit der Bedingung:
f(n) <= c * n

hier:
n² + 1 <= 100n
-> mit c=100 und n=1 würde herauskommen:
2 <= 100

Was ja korrekt ist... aber das kann ja eigentlich garnicht sein..... Wo mache ich was falsch?!

 

[Marco13]

Zu zeigen:
Exisitert c > 0, Stelle n >= 0 aus Natürlichen Zahlen mit der Bedingung:

für alle m>=n gilt f(m) <= c * m

 

[b1zarRe]

für alle m>=n gilt f(m) <= c * m

Sorry, stehe auf dem Schlauch... Welches m bzw. was meinst du genau? Danke vorrab schonmal

 

[Marco13]

Alle

Also, wenn du meinst, dass das im Beispiel mit c=100 und n=1 funktioniert, dann muss es für
m=n gelten:
f(m) = 1*1+1 = 2
c * m = 100*1 = 100
2 < 100 ? Passt

Es muss aber auch für m = 1000 gelten (eben für alle m>=n)
f(m) = 1000*1000+1 = 1000001
c * m = 100*1000 = 100000
1000001 < 100000 ? Passt NICHT


Bildlich gesprochen: Wenn man die Funktionen 'c*n' und f(n) plotten würde, dann müßte die Linie für f(n) irgendwann unerhalb der Linie von 'c*n' liegen, und auch für immer unterhalb dieser Linie bleiben.

 

[b1zarRe]

Ja ok, dass ist wohl war, nur wie hast du herausgefunden, dass es ab m = 1000 nichtmehr passen wird? Also, für c = 1 und n oder m = 100 hats ja gepasst... wielange muss ich ausprobieren bzw. wann sehe ich, dass es stimmt?

 

[muckelzwerg]

Eigentlich probierst Du das gar nicht aus. Höchstens um einen Widerspruch zu zeigen.
Für gewöhnlich schaust Du die Formel an, verwendest die üblichen Umformungsregeln und landest bei der entsprechenden Komplexität.
Ansonsten rechnest Du die Gleichung vor, um bspw. zu Zeigen dass n² +1 eben nicht in n liegt.
n² + 1 <= c * n
n² <= c*n
n* n <= c * n
n <= c
----> "kaputt". c ist eine Konstante, n ist nach oben unbeschränkt, "n <= c, für alle n" wird niemals wahr sein, also war die Gleichung zu Anfang bereits falsch.

 

[b1zarRe]

Danke euch

Ne Nacht drübber schlafen hat geholfen und endlich begriffen, danke

 

[b1zarRe]

Eine fragre hat sich noch ergeben:

f(n) = 2n + 1
f aus O(n^2)?

f(n) <= c * n^2
2n + 1 = 2n^2 + n^2 = 3n^2

Also ergibt sich c = 3 daraus fuerAlle n >= 0

So stand es im skript:
2 fragen hierzu:
1. Wie kommt kan auf die umformung? Bzw darf kan nur so umformen oder wie findet ihr das c, denn:
2. C= 2 wuerde auch schon funtionieren... Oder ist es egal ob c= 2 oder 3 ist und es nur wichtig ist, dass kan ein c gefunden hat???

 

[b1zarRe]

Hier noch ein Beispiel:

c*n <= n^2 + n <= d*n
Eigentlich sieht man schon mit bloßem Auge, dass n^2 stärker wächst(mit genügend großem n) als d*n... Wer in Mathe
fit ist, kann das sicherlich gut umstellen... ich weiß nicht ob es so erlaubt ist, aber ich würde es so machen:
c <= n^2 <= d //Überall das n weg
Und schon sieht man, dass die Variable n früher oder später größer sein kann und wird als irgendwelche Konstanten c und d...
Also falsch! n^2 + n nichtAus THETA(n)... <- Kann diesen Beweis jemand bestätigen?!

PS.: Sorry für die vielen Posts (( dachte ich kann das nachträglich löschen aber geht wohl immer nur der letzte Beitrag... Sorry :&

 

[SlaterB]

bei c = 2 nun n=1 wäre 3 < 2, also ist c = 2 nicht so gut, c sollte schon 3 sein, dann klappt es auch für n=1,
für n=0 hilft aber kein Faktor, da ist immer die 1 > 0, insofern ist "fuerAlle n >= 0" bei c=3 etwas komisch

zu dem anderen Beweis möchte ich persönlich nichts bestätigten oder revidieren,
aber ne andere Idee bzw. Umformulierung:
ein hohes n > d wählen, dann ist n^2 + n >= d*n + n, also ganz bestimmt >= d*n, egal welches d man annimmt,
n wird irgendwann immer größer als d, das sagst du ja auch, ist wohl ziemlich dasselbe

 

[b1zarRe]

Ist es denn "egal" welches c man nimmz oder MUSS man auf das kommen, welches am guenstigsten ist?gehst du da grnauso vor wie ich oder hase da noch tipps?

Mich wurmt zb die aufgabe: f + g aus O(max(f,g)).
Eigentlich total simpel, da einfach das "groesser wachsende" n genommen wird und somit muessn beide aus der aufwandsklasse sein; nur wie kann ich das formal beweisen ohne konkrete zahlenwerte?

 

[SlaterB]

du solltest zum c schon das passende zugehörige nc finden, so dass für alle n > nc die Sache läuft,
natürlich kann das recht hoch sein, einen möglichst kleinen Wert zu finden zeugt aber von Intelligenz und ist zu bevorzugen,

hier hat man die Wahl zwischen c = 2 und n>=2, c=3 und n>=1 sowie c =4, 5, 6, ... und n immer noch >=1,
was da nun das beste ist von den ersten beiden.., kann ich nicht vollständig sagen, anscheinend das zweite

zum anderen sage ich mal nix, wird mir zu formal, da habe ich nicht mehr alle Detailkenntnisse,
im Zweifel in normalen glaubwürdigen Sätzen beschreiben,
wenn es Formalismus zu lernen gibt, dann schaue in deine Unterlagen oder frage den Verantwortlichen

 

[b1zarRe]

Eine, wohl, letzte Frage noch zu dem Thema: Wenn ich zb ein Array habe und dann einen Zugriff auf EIN Element mache, ist das ja konstant also aus O(1). Wie ist das, wenn ich zb. 3 konstante Zugriffe habe? Schreibe ich dann O(3) oder heißt die Klasse O(1) und wird auch immer so geschrieben?

 

[Marco13]

Der Beweis, dass für beliebige natürliche Zahlen a und b gilt, dass O(a) = O(b) sei dem geneigten Leser als Übung empfohlen

 

[b1zarRe]

Der Beweis, dass für beliebige natürliche Zahlen a und b gilt, dass O(a) = O(b) sei dem geneigten Leser als Übung empfohlen

Falls ich dich richtig verstehe: ich will ja nicht aussagen, dass Konstante 1 = Konstante 5 ist.
Aber es könnte doch sein, dass man diese Konstante KLASSE mit O(1) beschreibt...

Immerhin sagt man bei O(n) auch nicht O(n+1) oder so... deswegen halt die Frage, was formal richtig ist??

 

[SlaterB]

die Liste der Komplexitätsklassen solltest du nun wirklich vorliegen haben oder schleunigst im Internet nachschlagen,
danach hier zu frage ergibt nun wirklich nichts neues mehr, alles Definitionssache

 

[Illuvatar]

Falls ich dich richtig verstehe: ich will ja nicht aussagen, dass Konstante 1 = Konstante 5 ist.
Aber es könnte doch sein, dass man diese Konstante KLASSE mit O(1) beschreibt...

Immerhin sagt man bei O(n) auch nicht O(n+1) oder so... deswegen halt die Frage, was formal richtig ist??

Du hast Marco falsch verstanden, glaube ich. Er wollte dir sagen, dass du Recht hast: dass tatsächlich O(1) = O(3) = O(5) = ... gilt. Man schreibt dann üblicherweise O(1).