Klausur 21.02.2008 - Aufgabe 9 O-Kalkül

Forum: Bachelor › Algorithmik › Algorithmen und Datenstrukturen

LaCucaracha Member since Jan 2012 43 posts	2012-02-20, 16:17 #1 Subject: Klausur 21.02.2008 - Aufgabe 9 O-Kalkül +0 +0 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	2012-02-20, 16:27 #2 +0 +0 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	2012-02-20, 17:42 #3 +0 +0 Ah, stimmt hast recht, ich hab das n vor dem log übersehen!

Guanta

Member since Oct 2005

307 posts

2012-02-21, 13:36 #4

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	2012-02-21, 14:57 #5 +0 +0 aber wurde nicht gesagt, dass es eigentlich immer das Elementzeichen beim O-Kalkül richtig ist, aber nur wiels handlicher ist = geschrieben wird?

Guanta Member since Oct 2005 307 posts	2012-02-21, 15:45 #6 +0 +0 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	2012-02-21, 23:57 #7 +0 +0 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

2012-02-22, 00:46 #8

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	2012-02-22, 09:09 #9 In reply to post #6 +0 +0 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

2012-02-22, 10:57 #10

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

Member since Oct 2005

307 posts

2012-02-22, 12:32 #11

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)

Go to forum

Datenschutz | Kontakt