Worst, Best, Average Case
Results 1 to 4 of 4
  1. #1
    leadpen's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Posts
    481
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Worst, Best, Average Case

    Hallo!

    Habe folgende Frage:
    Bei der Laufzeit-Analyse wird ja zwischen Best, Worst, und Average-Case unterschieden. Im Skriptum werden dann noch Begriffe wie Untere-, Obere- und Genaue-Schranke erläutert - hier liegt mein Problem:

    Gibt es für den Best-Case eine Obere, Untere- und eine Genaue-Schranke;

    Gibt es für den Worst-Case eine Obere, Untere- und eine Genaue-Schranke;

    Gibt es für den Average-Case eine Obere, Untere und eine Genaue-Schranke;

    Ich werd aus dem Skriptum einfach nicht schlau, für mich widerspricht sich alles was da drinnen steht.

    Bitte um hilfe,

    leadi

  2. #2
    Bomple's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Location
    Wien
    Posts
    333
    Thanks
    0
    Thanked 0 Times in 0 Posts
    in allen fällen gilt: ja

    die schranken geben nichts anderes als eine abschätzung für den aufwand bei steigenden datenmengen an und das kann man natürlich immer abschätzen (ausser bei problemen die np-vollständig sind, aber das ist wieder ein anderes thema)

  3. #3
    leadpen's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Posts
    481
    Thanks
    0
    Thanked 0 Times in 0 Posts
    man dankt...


    leadi

  4. #4
    Lord Binary's Avatar
    Title
    Dipl.Ing
    Join Date
    Dec 2003
    Location
    Wall Street
    Posts
    1,183
    Thanks
    93
    Thanked 19 Times in 13 Posts
    (ausser bei problemen die np-vollständig sind, aber das ist wieder ein anderes thema)
    Nein!
    Die Existenz von Schranken für best/average/best case hat wenig bis nix mit der komplexitätstheoretischen Einordnung des Problems (das ein bestimmter Algorithmus löst) zu tun.
    Zumindest bei entscheidbaren Problemen.

    Mfg, LB
    Last edited by Lord Binary; 18-04-2004 at 16:16.

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
  •