Was dekt ihr über diese Laufzeitabschätzung?
Results 1 to 9 of 9
  1. #1
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts

    Was dekt ihr über diese Laufzeitabschätzung?

    Von letzter Prüfung:

    k=n;
    wiederhole
    k=k/2;
    l=n*k;
    bis k=l

    Also ich hätte gesagt das liegt in Theta(n²)... bin mir aber nicht sicher. Was sagt ihr? Könnte auch Theta(n log n) sein. Hmmm...
    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  2. #2
    dose's Avatar
    Title
    Dipl.Ing
    Join Date
    Feb 2002
    Location
    Meidllling
    Posts
    1,037
    Thanks
    1
    Thanked 0 Times in 0 Posts
    Die Schleife wird bei Zweierpotenzen genau log n mal durchlaufen, bei non-Zweierpotenzen (log n)-1 mal, daher:
    Theta(log n)
    yast, SuSEconfig, apt-get and rpm - the 4 horsemen of the apocalypse

    Platform of insanity :: www.dose-xp.org

  3. #3
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    Ja aber schau dir mal den Teil an:

    l=n*k;
    bis k=l
    Da muss man ja das l, die Abbruchbedingung) auch mitberücksichtigen, weil die sich auch immer durch n ändert
    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  4. #4
    Shade's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Posts
    484
    Thanks
    0
    Thanked 0 Times in 0 Posts
    die frage ist ,ob das überhaupt erfüllbar ist.gibt es denn eine zahl die genau denn gleichen wert hat wenn ich sie halbiere bzw. quadriere.ich kenn keine(ausser 0).daher mein tipp: endlossschleife für alle zahlen ungleich 0.wenn du für die prüfung lehrnen willst musste so schwere sachen sicher nicht wissen.
    ALL GLORY TO THE HYPNO TOAD...

  5. #5
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    Das mit der Endlosschleife hab ich mir auch gedacht...

    Anscheinend sollen wir sowas schon wissen, da das ja ein Bsp. der letzten Prüfung ist... Könnte natürlich auch sein, dass derjenige ders ins Netz gestellt hat sich verschrieben hat o.ä. ?

    Auf jeden Fall verwirrt mich das Ding
    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  6. #6

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts
    nachdem l=n*k ist kann l==k natürlich nur stimmen, wenn k=0 - und k wird wenn man abrundet nach genau ld(n) bzw. ld(n)+1 schleifendurchläufen 0 (nehme an man soll abrunden, sonst ist es eine endlosschleife).

    stimme daher dose zu, das sollte theta(log n) sein.
    Last edited by Lukas; 10-10-2002 at 22:48.

  7. #7
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    Ok dank euch, denk ich hab den Ansatz verstanden... aber is ein gemeines Klump, das!
    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  8. #8
    Jokeman's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Location
    near Vienna
    Posts
    210
    Thanks
    0
    Thanked 0 Times in 0 Posts
    also ich glaub, dass das ein abschreibfehler war
    Command & Conquer
    =Return of the Dawn=

    TS to TD total conversion

  9. #9
    dose's Avatar
    Title
    Dipl.Ing
    Join Date
    Feb 2002
    Location
    Meidllling
    Posts
    1,037
    Thanks
    1
    Thanked 0 Times in 0 Posts
    Hab das l=k falsch interpretiert als l=n, also isses, wie Lukas schon gesagt hat (log n)+1 bzw. (log n), daher Theta(log n)
    yast, SuSEconfig, apt-get and rpm - the 4 horsemen of the apocalypse

    Platform of insanity :: www.dose-xp.org

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
  •