WS 02 Loesung
Results 1 to 6 of 6

Thread: WS 02 Loesung

  1. #1

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts

    WS 02 Loesung

    - Beispiele 8, 9 und 10 wurden hinzugefuegt
    - bei Beispiel 8 wurde die Fehlende Antwort fuer die Teilfrage hinzugefuegt
    - Bei Aufgabe 6 fehlte ebenfalls die Antwort auf eine Teilfrage
    - Beispiel 4 ausfuehrlicher erklaert
    - Aufgabe 3b wurde korrigiert

    Seit 18.10.02, 19:30 ist die Version 0.6 online unter uebung.html
    Last edited by yrucrem; 18-10-2002 at 20:32.

  2. #2

    Title
    Veteran
    Join Date
    Oct 2002
    Posts
    24
    Thanks
    0
    Thanked 0 Times in 0 Posts

    aufgabe 3b)

    bist du dir bei 3b) sicher?

    die zeile "j = j + i"; wird insgesamt ~ 2n + 26 log n mal ausgeführt;
    die zeile m = m/2 ... ~ log n mal

    daher würde ich sagen b) ist ebenfalls Theta (n) - auch wenns auf den ersten blick nicht so ausschaut

    greetz
    Steve

  3. #3

    Title
    Dipl.Ing
    Join Date
    May 2002
    Posts
    1,074
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Kann mir jemand sagen, wie ich die Bspe nach 3 Vorlesungen verstehen soll? Ich find das schon etwas blöd. Möchte mich aber für die Lösungen bedanken, ohne den es völlig sinnlos wäre.

    mfg crow

  4. #4

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    > die zeile "j = j + i"; wird insgesamt
    > ~ 2n + 26 log n mal ausgeführt

    Die Formulierung ist mir etwas unklar. Meintest du das so: (2n + 26) log n? Das ist aber dann auch \Theta(n log n).

    Ich bin mir eigentlich schon sicher. Die innere Schleife ist linear. Die aeuszere ist logarithmisch. Die innere Schleife wird \Theta(log n) mal ausgefuehrt und ist selber in \Theta(n) --> \Theta(n log n).

    Als ich bei der Einsichtnahme fuer den Test war, habe ich gefragt, ob man sich das so vorstellen kann, und es ist anscheinend richtig. Ich werde jedenfalls mal versuchen eine einsichtige Erklaerung (oder Widerlegung ;-)) zu finden.

    /edit 18.10.02:
    Slater hat recht, es ist in \Theta(n). Tja man sollte eben nicht immer die Musterloesungen glauben ;-).
    Last edited by yrucrem; 18-10-2002 at 20:33.

  5. #5

    Title
    Veteran
    Join Date
    Oct 2002
    Posts
    24
    Thanks
    0
    Thanked 0 Times in 0 Posts
    die einzelnen durchläufe der inneren schleife sind zwar linear... aber wenn du beide schleifen zusammen betrachtest dann schauts doch so aus:

    (n + 26) + (n/2 + 26) + (n/4 + 26) + (n/8 + 26) ... usw

    n + n/2 + n/4 ... usw entspricht ~ 2n

    dann bleiben nur noch die 26 zusätzlichen durchläufe der inneren schleife für log n durchläufe der äusseren

    deswegen ~ 2n + (26 log n)
    und nachdem die ordnung von n größer is als von log n (siehe mathe 1 ;) sollte das ganze Theta (n) sein - soweit ich das verstehe

  6. #6

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    Tja, stimmt. Das ganze ist in \Theta(n). *schrecklichrotwerd* Ich haette mich nicht so auf n log n versteifen sollten. Tja man sollte eben nicht immer die Musterloesungen glauben ;-).

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •