Not logged in. · Lost password · Register

LaCucaracha
Member since Jan 2012
43 posts
Subject: Klausur 21.02.2008 - Aufgabe 9 O-Kalkül
Wer möchte Ergebnisse vergleichen?
a)

1) O (log n)
2) O (n²) --> Hier hab ich allerdings keinen Schimmer was k bedeuten soll
3) O (n²)
4) O (n)
5) O (n³)

b)
ja, ja, nein, ja
kaut
Member since May 2011
380 posts
also a) hab ich genauso

und bei b hab ich:

ja, ja, nein, nein (wobei ich mir bei dem 2. ja nicht sicher bin).
LaCucaracha
Member since Jan 2012
43 posts
Ah, stimmt hast recht, ich hab das n vor dem log übersehen!
Guanta
Avatar
Member since Oct 2005
307 posts
bei der a)2) muss es glaube ich eher O(n) heißen, es steht nicht da was k ist --> im Allgemeinen beschneidet k die eine Schleife -> O(n). Rest passt.
bei der b) hätte ich gesagt, ja, nein, nein, nein, aber die zweite Angabe ist indeed etwas streitwürdig, wenn da das Element-Zeichen statt '=' stehen würde wäre es wohl richtig, so wies dasteht ists aber imho falsch (kein Plan wie sies bewertet haben)
An eye for an eye will make the whole world blind. (Gandhi)
bewi1992
Member since Oct 2011
189 posts
aber wurde nicht gesagt, dass es eigentlich immer das Elementzeichen beim O-Kalkül richtig ist, aber nur wiels handlicher ist = geschrieben wird?
Guanta
Avatar
Member since Oct 2005
307 posts
Hier wird aber nicht das ∈ ersetzt, korrekterweie müsste es imho heißen: O(fg) ⊃ f * O(g). Aber so genau kenn ich mich damit auch nicht aus.
An eye for an eye will make the whole world blind. (Gandhi)
This post was edited on 2012-02-21, 15:47 by Guanta.
???
Member since Oct 2011
445 posts
Warum ist es denn bei der b beim 4. nicht ja sondern nein, weil ich dachte in O(n) liegen auch alle anderen oberern Schranken, die größer sind als n oder? und n*logn ist doch immer größer als n (ab einem n) und dann wäre die Aussage doch richtig oder?
Mich
Member since Dec 2008
337 posts
Quote by ???:
n*logn ist doch immer größer als n (ab einem n)

Ja eben. f(n) in O(g(n)) wenn fuer alle x : f(x) <= c*g(n) (x->inf, c>0) und wie du schon gesagt hast ist n*log(n) > n also ist n*log(n) _nicht_ in O(n), ergo ist O(n*log(n)) auch nicht echte Teilmenge von O(n), sonst muesste ja eine Funktion die in O(n*log(n)) liegt auch in O(n) liegen und das ist nicht der Fall. (EDIT: Anders herum gilt es z.B. was in O(n) liegt liegt auch automatisch in O(n*log(n)))
This post was edited on 2012-02-22, 00:48 by Mich.
ellewoods
Member since Nov 2011
45 posts
In reply to post #6
Quote by Guanta:
Hier wird aber nicht das ∈ ersetzt, korrekterweie müsste es imho heißen: O(fg) ⊃ f * O(g). Aber so genau kenn ich mich damit auch nicht aus.

Aber auf Folie 5-24c) im Skript steht doch dass die Aussage stimmt? Und damit wäre Ausage 2 von b) doch richtig!
This post was edited on 2012-02-22, 09:10 by ellewoods.
???
Member since Oct 2011
445 posts
In reply to post #8
Quote by Mich:
Quote by ???:
n*logn ist doch immer größer als n (ab einem n)

Ja eben. f(n) in O(g(n)) wenn fuer alle x : f(x) <= c*g(n) (x->inf, c>0) und wie du schon gesagt hast ist n*log(n) > n also ist n*log(n) _nicht_ in O(n), ergo ist O(n*log(n)) auch nicht echte Teilmenge von O(n), sonst muesste ja eine Funktion die in O(n*log(n)) liegt auch in O(n) liegen und das ist nicht der Fall. (EDIT: Anders herum gilt es z.B. was in O(n) liegt liegt auch automatisch in O(n*log(n)))

ah cool danke :)
Guanta
Avatar
Member since Oct 2005
307 posts
In reply to post #9
Quote by ellewoods:
Quote by Guanta:
Hier wird aber nicht das ∈ ersetzt, korrekterweie müsste es imho heißen: O(fg) ⊃ f * O(g). Aber so genau kenn ich mich damit auch nicht aus.

Aber auf Folie 5-24c) im Skript steht doch dass die Aussage stimmt? Und damit wäre Ausage 2 von b) doch richtig!

Vorsicht, so wies im Script: O(f(n))*O(g(n)) = O(f(n)*g(n)) ist es auch richtig, aber in der Klausur stand es ja O(f(n)*g(n)) = f(n)*O(g(n)), was imho formal falsch ist (auch wenn es gut sein kann, dass sie das als richtig interpretiert haben, kA).
An eye for an eye will make the whole world blind. (Gandhi)
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen