AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein Die Groß-O Notation im worst case.
Thema durchsuchen
Ansicht
Themen-Optionen

Die Groß-O Notation im worst case.

Ein Thema von Kanikkl · begonnen am 20. Dez 2009 · letzter Beitrag vom 20. Dez 2009
 
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#2

Re: Die Groß-O Notation im worst case.

  Alt 20. Dez 2009, 03:11
Erstmal den Link zu Wikipedia: http://de.wikipedia.org/wiki/Landau-Symbol

Dort findet man eine Definition für O( g ) ähnlich der folgenden:
f ∈ O(g) genau dann wenn http://upload.wikimedia.org/math/6/2...381ebc7386.png

Grafik frei übersetzt:
Es existiert ein c > 0 und ein x_0 so, dass für alle x > x_0 gilt |f(x)| <= c*|g(x)|
Ein solches c und x_0 findest du aber nicht für alle Kombinationen von f und g.

Beispiel 1:
Egal, wie (hoch) du c und x_0 wählst, es wird immer ein x >= x_0 geben, so dass |x²| > c*|x| (z.B. x = max(c+1, x_0+1) ).
Also ist gilt x² ∉ O(x)

Um zu zeigen das ein f ∈ O(g) ist, musst du ein x_0 und ein c finden, so dass die obige Definition zutrifft.

Beispiel 2:
Wir vermuten das 2x²+5x+6 ∈ O(x²) ist.

Also wollen wir ein x_0 und ein c > 0 finden, für das gilt:
|2x²+5x+6| < c*|x²| für alle x > x_0

Wir sehen, dass x besser nicht 0 sein sollte, also sagen wir: x_0 ist größer 0:
x_0 > 0

Als praktische Beigabe ergibt sich, dass die Terme in den Betragsstrichen jetzt immer positiv sind, d.h. können wir sie weglassen.

2x²+5x+6 < c*x²

Nun versuchen wir ein c zu finden für das die obige Ungleichung gilt:
2x²+5x+6 < c*x² # -2x²
5x+6 < (c-2)x² # /x² (geht problemlos, da x > x_0 > 0)
(5x+6)/x² < c-2
5/x + 6/x² < c-2
Nun setzen wir x_0 := 10, womit gilt 5/x + 6/x² < 1.
Jetzt suchen wir uns ein c, so dass c-2 >= 1, zum Beispiel c := 1 3

Damit haben wir ein x_0 = 10 und ein c = 1 gefunden, so dass |2x²+5x+6| < c*|x²| für alle x > x_0 gilt.
Also gilt laut Definition: 2x²+5x+6 ∈ O(x²)

So, ich finde, mehr sollte in der Infoklausur mathematisch nicht von euch verlangt werden

Ich hab das Ganze eigentlich nur geschrieben, weil du explizit N (=x_0) und C (=c) erwähnt hast,
fände soviel Mathematik in der 12. im Informatikkurs aber etwas merkwürdig
Bist du sicher, das du weißt, was euer Lehrer von euch will?

Disclaimer:
Ich hab mir zwar Mühe gegeben keine großartigen Fehler einzubauen, erhebe aber keinen Anspruch auf Korrektheit.
Falls jmd. Fehler findet, unbedingt melden (nicht dass mir das im März in der Klausur aufstößt ).

MfG,
Bug
Intellekt ist das Verstehen von Wissen. Verstehen ist der wahre Pfad zu Einsicht. Einsicht ist der Schlüssel zu allem.
  Mit Zitat antworten Zitat
 


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 22:22 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz