Not logged in. · Lost password · Register

peck
Member since Jul 2010
16 posts
Subject: O Kalkül 31.07.2008
Aufgabe 9
Sind meine Ergebnisse richtig? Wenn nein, warum nicht? Ich hab:
a)

1. O(n)

2. O(n²)

3. O(n²)

4. O(n * log n)

5. O(n²)


b)

f: O(1)

fac: O(n)

hanoi: O(n)


c)
1. keine ahnung
2. ja
Tuchkata
Member since Oct 2009
45 posts
9a.1: O(n)
9a.2: O(n²)
9a.3: O(n²)
9a.4: n * log n
9a.5: O(n)

9b.1: O(1)
9b.2: O(n)
9b.3: O(x^n)

9c.1: Nein
9c.2: Ja
:)
educs
Member since Jul 2010
64 posts
Die a hab ich identisch gelöst.

Bei der b hab ich beim ersten auch O(1).
fac und hanoi weiß ich nicht, wie man die löst. Ebenso die c1. Kann das jemand mal erklären bitte?

Bei der c2 hatte ich auch ja.
knix
Avatar
Member since Oct 2009
242 posts
Quote by educs:
fac und hanoi weiß ich nicht, wie man die löst.

fac():
Bei jedem Rekursionsschritt vermindert sich der Parameter um 1 und fac() mit dem verminderten n einmal aufgerufen.
=> Es wird also n-mal die fac() Methode aufgerufen => O(n)

hanoi():
Der Methode hanoi wird der Parameter n übergeben.
Jeder Aufruf der Methode hanoi() resultiert in 2 weiteren Aufrufen (Stichwort: exponentiell) mit einem um 1 verminderten n.
=> O(x^n) (Zeichne einfach mal den Baum, das hilft oft ;) )
just the BEST theorem: ec(G) = tᵤ(G) ∏(deg(v) - 1)!
tante emma
Avatar
Member since Apr 2010
14 posts
Unter der Gefahr eine dumme Frage zu stellen:
Warum steht da überhaupt void f(int n) und dann return ..;? Seid ihr davon ausgegangen dass es sich um einen Druckfehler handelt und es heißen müsste int f(int n) { return ...;}? Frage mich die ganze Zeit ob das ne Fangfrage ist  :nuts:
meisterT
Member since Nov 2005
994 posts
sieht mir nach nem Fehler in der Angabe aus
FAU Online Judge
joe
Member since Jul 2010
14 posts
Es ist glaub ich kein Angabenfehler (siehe Kapitel 8 Seite 29).

warum habt ihr eigentlich alle bei der 9b.3 O(x^n). Müsste das x nicht gleich 2 sein?
Also 9b.3: O(2^n).
meisterT
Member since Nov 2005
994 posts
Quote by joe:
Es ist glaub ich kein Angabenfehler (siehe Kapitel 8 Seite 29).

Was hat die Fibonacci-Funktion mit einem falschen return-Typ (void statt int) zu tun?
FAU Online Judge
joe
Member since Jul 2010
14 posts
Stimmt stimmt! Hab erst jetzt das void gesehen. xD
Danieru
Member since Nov 2009
258 posts
for (int i = 0; i < n; i++)
  for (int j = 0; j < i; j++)
    f(i,j);

steh gerad auf den Schlauch warum O(n²), i ist doch immer kleiner n :\
meisterT
Member since Nov 2005
994 posts
Du kannst dir ueberlegen, wie oft f(i,j) aufgerufen wird.
Das ist 0 mal fuer i=0, 1 mal fuer i=1, 2 mal fuer i=2...

f(i,j) wird also 0+1+2...+(n-2)+(n-1) mal aufgerufen. Gemaess Gauss'scher Summenformel kann man das reduzieren auf ((n-1)*n)/2. Nun kann man anhand der Rechenregeln im O-Kalkuel auf O(n^2) vereinfachen. (Angenommen f(i,j) kann man in O(1) berechnen.)
FAU Online Judge
educs
Member since Jul 2010
64 posts
Ich hänge noch bei der hanoi Methode.
Kann das jemand nochmal genauer erklären, wie man da auf x^n kommen soll?
rudis
SPler
(Administrator)
Member since Apr 2010
646 posts
Ich hoffe mal das void war keine Fangfrage, aber ich haette das einfach ignoriert. Weil so wuerde es ja gar nicht kompilieren.

Muesste die a5) nicht O(n) sein? Weil es werden jedesmal 10 Schritte (von i bis i+10) ausgefuehrt.

Bei Hanoi hab ich auch O(2^n).
neverpanic
Member since Sep 2008
1458 posts
Quote by rudis:
Muesste die a5) nicht O(n) sein? Weil es werden jedesmal 10 Schritte (von i bis i+10) ausgefuehrt.
Natürlich. Tuchkata hat das oben ja auch schon richtig erkannt.
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