Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

XeeLee

Praktikant

  • "XeeLee" started this thread

Posts: 29

Date of registration: Jul 21st 2010

1

Friday, September 2nd 2011, 3:54am

KvA Übungsfragen SoSem 2011

Kann mir jemand evtl. helfen die Groß-O Zugehörgkeit richtig zu verstehen. In der Ü1A1 b) müssten wir zeigen, dass n^2 zu O(n) gehört. Dies haben wir wiederlegt indem wir gezeigt haben, dass n^2 <= c * n ist, was und zur Aussage führt, dass c >=n ist, und dass ist ein Wiederspruch, weil c nicht konstant ist. Somit gehört n^2 nicht zu O(n). Damit komme ich noch klar, aber wenn ich mir weiter die Punkte d), e), f) ansehe, dann bekomme ich folgende Aussagen für c:
  • d) c >= (n / log (n))
  • e) c >= (log (n) / n)
  • f) c >= (3/2)^n
Diese Lösungen sehen für mich alle nicht nach einem konstanten c. In der Übungsstunde haben wir damals notiert, dass d) nicht stimmt und e), f) stimmen. Jetzt sehe ich aber kein Unterschied mehr, weil ja überall c nicht konstant ist?
  • Send private message

Kater

Trainee

  • "Kater" is male

Posts: 93

Date of registration: Sep 29th 2009

2

Friday, September 2nd 2011, 7:23am

c ist immer konstant, aber beliebig. Man prüft nicht, ob c konstant ist oder nicht, sondern, ob c die Gleichung erfüllen kann. Hierbei muss es dannnur nur ein best. c geben für das die Gleichung, ab einem bestimmten n gilt.

zu d) n ist größer als log n. Daher geht das Ganze gegen unendlich, wenn man n immer größer werden lässt. Also kann eine Konstante nicht im allg. größer sein, da sie irgendwann eingeholt wird.
zu e) hier ist es genau anders herum. Also geht das ganze gegen 0, wenn man n immer größer werden lässt. Daher kann eine Konstante größer sein, da irgendwann die Funktion niedriger wird als die Konstante.
zu f) So ist das nicht erfüllt, da (3/2)^n gegen unendlich geht, wenn man n immer größer werden lässt. Also kann eine konstante nicht im allg. größer sein, da sie irgendwann eingeholt wird.
Bei (2/3)^n würde das wieder anders aussehen. Dann geht das wieder gegen 0.

This post has been edited 5 times, last edit by "Kater" (Sep 2nd 2011, 7:39am)

  • Send private message

XeeLee

Praktikant

  • "XeeLee" started this thread

Posts: 29

Date of registration: Jul 21st 2010

3

Friday, September 2nd 2011, 1:45pm

Also prüft man wohin wandert das Limit, wenn man n gegen unendlich wachsen lässt, und ob es eine Zahl existiert, die größer ist, als Limit bei n gegen unendl. So macht es natürlich Sinn :-) Vielen Dank!

This post has been edited 1 times, last edit by "XeeLee" (Sep 2nd 2011, 1:46pm)

  • Send private message