O-Notation, bezogen auf Informatik

Neue Frage »

Kathreena Auf diesen Beitrag antworten »
O-Notation, bezogen auf Informatik
Ordnen Sie folgende Komplexitätsklassen aufsteigend und kennzeichnen Sie gleichmächtige
Komplexitätsordnungen (log bezeichnet den Logarithmus zur Basis 10, ld bezeichnet den
Logarithmus zur Basis 2). Begründen Sie Ihre Antwort exemplarisch mit Hilfe der Definition
der O-Notation.













Meine Idee:
Ich hoffe das nich so verkehrt ist, das in dieses Forum zu posten.

Die Definition die ich habe ist:



Also so wie ichs verstanden habe ist dieses groß O die obere Schranke.

Wenn ich die Klassen aufsteigend ordnen soll, wäre ich so vorgegangen, ich plotte einfach mal alle Funktionen, und schau welche am schnellsten gegen unendlich gehn, oder welche eventuell sogar nen Grenzwert haben. Dann komm ich auf:



Nur wie begründe ich das nun.
HAL 9000 Auf diesen Beitrag antworten »

Die Reihung ist soweit richtig, aber: ist ja eine Menge von Funktionen , die der entsprechenden Landau-Bedingung genügen.

Im dem Sinne solltest du es besser mit dem passenden Mengenoperator schreiben:



Das kann man dann so lesen: Für jede Funktion gilt auch , usw.

Wie weist man nun diese Kette nach? Nun, hinreichend für wäre auf jeden Fall . Das kannst du hier der Reihe nach abklappern.


P.S.: Dein ist zwar nicht falsch, aber unnötig unpräzise - beide Funktionsklassen sind gleich.
 
 
zweiundvierzig Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
P.S.: Dein ist zwar nicht falsch, aber unnötig unpräzise - beide Funktionsklassen sind gleich.

Ebenso könnte man O(log(n^2)) = O(log(n)) und O(2n) = O(n) vereinfachen, wenn auch nicht explizit gefordert.
Kathreena Auf diesen Beitrag antworten »

Danke, ja dachte ich mir schon. Ja muss das auf die einfachste Form bringen, auch wenns nicht in der Angabe steht.

Sollte es nun selber hinbekommen.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »