Beweis O-Notation

rogue

rogue

Mitglied
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.
 
M

Marco13

Top Contributor
thorstenthor hat gesagt.:
c) kann ich nicht so recht glauben, wenn 2 und 3 Exponenten sind.
Zum Vergrößern anklicken....

Na und? Was meinst du, wie viele Studenten es trotzdem schaffen, das zu beweisen :D

Die relevante Formel aus Wikipedia ist
957835bd772048b5304bcae3ede77e44.png


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)
 
rogue

rogue

Mitglied
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?
 
M

Marco13

Top Contributor
@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 :rolleyes: )

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 :D 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...
 
M

muckelzwerg

Bekanntes Mitglied
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. :)
 
F

Firephoenix

Gast
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ß
 
T

thorstenthor

Bekanntes Mitglied
Marco13 hat gesagt.:
Na und? Was meinst du, wie viele Studenten es trotzdem schaffen, das zu beweisen :D
Zum Vergrößern anklicken....

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.
 
M

Marco13

Top Contributor
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 :D )
 
T

thorstennn

Gast
Marco13 hat gesagt.:
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))
Zum Vergrößern anklicken....

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
 
I

iJuelz

Mitglied
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...
 

Aktuelle Jobs

Neue Themen


Oben