# Beweis O-Notation



## rogue (29. Jun 2011)

Hy,

ich hab leider ein Problem mit dem Beweis einer O-Notation. Wollte deshalb fragen ob ih mir vielleicht einen kleinen Denkanstoss geben könnt. Ich kapiere es noch immer komplett nicht. Landau-Symbole bei Wikipedia hat mir auch nicht os richtig weiter geholfen. 

Folgende Aufgabe haben wir gestellt bekommen:

Zeigen Sie, daß die folgenden Aussagen wahr sind.
a) 27 ist O(1)
b) n(n-1)/2 ist O(n2)
c) max(n3,10n2)ist O(n2)

Bin Dankbar über jeden Denkanstoss.


----------



## thorstenthor (29. Jun 2011)

Beim Ersten nimmste z.B. als Konstante 27, dann gelten die Definitionen...

c) kann ich nicht so recht glauben, wenn 2 und 3 Exponenten sind.


----------



## Marco13 (29. Jun 2011)

thorstenthor hat gesagt.:


> c) kann ich nicht so recht glauben, wenn 2 und 3 Exponenten sind.



Na und? Was meinst du, wie viele Studenten es _trotzdem_ schaffen, das zu beweisen 

Die relevante Formel aus Wikipedia ist 






Für den zweiten Fall
n(n-1)/2 ist O(n2)
müßtest du also z.B. ein 'n' finden, ab dem das Linke immer kleiner ist als das rechte (und dann beweisen, dass das so ist)


----------



## thorstenthor (29. Jun 2011)

Marco13 hat gesagt.:


> Na und? Was meinst du, wie viele Studenten es _trotzdem_ schaffen, das zu beweisen



was soll der ton? wenn für dich nhoch3 in n^2 ist, will ich den beweis gar nicht sehen. und wenn das keine exponenten sind, liegts an rogue, nicht an mir.


----------



## rogue (29. Jun 2011)

Hallo,

und danke für die Hilfe. Hatte leider vergessen die Aufgabe richtig zu schreiben. So sind sie richtig:

b) n(n-1)/2 ist O(n^2)
c) max(n3,10n^2)ist O(n^2)

Sorry wenn ich mich ein bisschen dumm anstelle. Wäre es so richtig bei 2?

Ich wähle z.B. 1 für n. So würde ja rauskommen

f(n) = 0

O(n) = 1

Hätte ich es damit schon bewiesen?


----------



## Marco13 (29. Jun 2011)

@thorstenthor: Auch wenn ich üblicherweise und tendenziell nicht auf offentlichliche Überempfindlichkeiten in bezug auf irgendwelche Formulierungen eingehe, erwähne ich hier doch mal, dass sich das darauf bezog, dass bei so einer Aufgabe ja schon eine Richtung vorgegeben ist, wenn sie anfängt mit den Worten "Zeige, dass...", und nicht etwa den Worten "Prüfe, ob...". Oder anders: Wenn man einem Studenten die Aufgabe gibt, zu beweisen, dass "max(n^3,10n^2) in O(n^2)" ist, dann gibt es sicher etliche, die so lange rumfrickeln, bis sie einen Beweis haben, der überzeugend darlegt, dass das so ist - schließlich war es die _Aufgabe_, zu zeigen, _dass_ es so ist (auch wenn es eben nicht so ist  ) 

Aber zum Thema: Das erinnert an den Beweis, dass alle Zahlen Primzahlen sind: 1 ist eine, 2 ist eine, 3 ist eine, also werden die restlichen wohl auch welche sein  Entscheidend ist hier, dass man beweisen muss, dass f(n) < c*g(n) für _alle_ n gilt, die größer sind als ein bestimmtes n. 

Also für f(n) = n*(n-1)/2 
und g(n) = n^2
hat man 
f(1) = 0
g(1) = 1
Es KÖNNTE ja aber sein, dass z.B.
f(10) = 10000 
g(10) = 100
gilt, dann wäre die Aussage ggf. nicht unbedingt erfüllt. 

Man könnte (spontan, aus dem Bauch raus) versuchen, das mit Induktion zu beweisen...


----------



## muckelzwerg (29. Jun 2011)

Rogue wie sollte man so eine Aufgabe denn ganz allgemein lösen? Habt ihr noch keine Beispielaufgaben gemacht?
Was für ein Beweisverfahren bietet sich denn an.
Ich hab das Gefühl, Dir fehlen nicht nur Weg und Ziel, sondern auch ob Du laufen, schwimmen oder fliegen sollst.

Versuch es doch mal mit einem direkten Beweis.
Schreib die Formel, die gelten soll hin und wende so lange Termumformungen an, bis es eindeutig stimmt oder eben nicht.
n(n-1)/2 = O(n^2) bedeutet doch
|n(n-1)/2| <= c * |n^2|
Das lässt sich doch recht schnell umformen, so dass es passt. Da kommst Du bestimmt selbst drauf.


----------



## Firephoenix (29. Jun 2011)

Hi,
für die 2. könnte man das auch anders angehen.
wähle als konstante 3, dann ist 3n elemtent von O(n) und O(n) ist in O(n^2),
wählst du als konstante 10, ändert sich an der 1. Aussage nichts, größer kann sie ja werden.
Dann ist allerdings 10n^2 auch in O(n^2).
Da das maximum immer einer dieser 2 Werte sein muss ist auch max O(3n, 10n^2) in O(n^2)
Gruß


----------



## thorstenthor (30. Jun 2011)

Marco13 hat gesagt.:


> Na und? Was meinst du, wie viele Studenten es _trotzdem_ schaffen, das zu beweisen



sorry. ich hab das nich verstanden.. deshalb ironie immer kennzeichnen..(so wie auch wikipedia angegeben  ). ich bin anscheinend nicht schlau genug, das zuverstehen.

btt:

termumformungen bei nicht zu komplizierten sachen klingt plausibel, so würd ich das auch machen.


----------



## Marco13 (30. Jun 2011)

Beim letzten könnte man vermutlich auch irgendwelche Rechenregeln verwenden - wie schon angedeutet wurde, sowas wie
Wenn
a(n) € O(f(n)) und
b(n) € O(g(n)) und
f(n) € O(g(n))
dann
max(a(n), b(n)) € O(g(n))
(Achtung, früh am morgen, wenig Koffein, das ist formal so sicher nicht "richtig" - aber solche allgemeinen Rechenregeln für max, min und Schachtelung gibt's garantiert irgendwo - und wenn nicht, dann stellt man sie auf und beweist sie, dafür kriegt man Fließ-Bienchen  )


----------



## thorstennn (30. Jun 2011)

Marco13 hat gesagt.:


> Wenn
> a(n) € O(f(n)) und
> b(n) € O(g(n)) und
> f(n) € O(g(n))
> ...



max(a(n), b(n)) € O(g(n)) gdw.,
a(n) € O(g(n)) und b(n) € O(g(n)),
würde sinn machen.

Allerdings muss man da mit der Trichotomie aufpassen, denn die gilt für die O-Notationen nicht. Somit kann max(a(n), b(n)) € O(g(n)) nicht immer entscheidbar sein. Entscheidbar ist aber im mathematischen Sinn auch nicht der richtige Begriff. hmm


----------



## thorstenthor (1. Jul 2011)

hier lesen: http://www.mathe.tu-freiberg.de/~ernst/Lehre/AD/Folien/adKapitel2.pdf

und hier: YouTube - ‪Algorithms Lesson 6: Big O, Big Omega, and Big Theta Notation‬&rlm;

hoffentlich darf man das einfach so verlinken. war der erste terefer bei google.


----------



## iJuelz (23. Jan 2013)

Hi wollte auch mal nach Hilfe fragen, habe folgende Aufgabe

"a. Weisen Sie für folgende Funktion die O-Notation nach.

f(x) = 7x²+x+15/4

Finden Sie Konstanten, dass folgende Bedingung erfüllt ist:

0 <= c1 x² <= f(x) <= c2 x²"


hoffe ihr könnt mir helfen...


----------

