Hi alle zusammen,
ich wollte mal fragen, was die Average Case Laufzeit ist, ist das (Worstcase + Bestcase)/2?
MfG Andi
PS: Wäre cool, wenn Ihr noch heute antworten könntet, aber bin trotz Zeitdruck froh um jede Antwort.
ich wollte mal fragen, was die Average Case Laufzeit ist, ist
das (Worstcase + Bestcase)/2?
Das ist einfach der Fall, in dem die Daten mit denen ein Algorithmus arbeitet „erwartungsgemäß“ sind. So gibt es z.B. bei Sortieralgorithmen die untere Schranke O(n) (jedes Element muss betrachtet werden), die praktisch nur bei bereits sortiert vorliegenden Daten erreicht wird und wo Bubblesort dann alle anderen Algorithmen plattmacht und je nach Algorithmus eine obere Schranke von z.B. O(n^2) wenn die Daten am ungünstigsten angeordnet sind, also z.B. invers sortiert. Erwarten wird man eine eher zufällige Verteilung, bei der dann die erwartete Laufzeit von z.B. O(n log n) erreicht wird.
Das ganze zu bestimmen ist ein wenig schwammig, weil man ja erkennen muss, für welche Fälle der betrachtete Algorithmus besonders gut oder schlecht läuft und wie die Eingabedaten wahrscheinlich aussehen.
Landau Symbole un O Notation
Hi ho,
So gibt es z.B. bei Sortieralgorithmen die untere Schranke O(n)
Wenn von O(n) die Rede ist, so meint man die asymptotisch Obere Schranke. Bei der asymptotisch unteren Schranke nimmt man als Symbol das Omega.
Genaueres dazu unter http://de.wikipedia.org/wiki/Landau-Notation
Da gibt es auch einen Link zu einem meiner Meinung nach sehr guten Artikel hier
http://www.linux-related.de/index.html?/coding/o-not…
Viele Grüsse,
Herb
Hallo Andreas,
hier mal ein kurzes Zitat dazu:
„…Auf den ersten Blick scheint es sinnvoller zu sein, die durchschnittliche Laufzeit des Algorithmus für ein Problem der Größe N zu bestimmen, also eine Average-case-Analyse durchzuführen. Es ist aber in vielen Fällen gar nicht klar, worüber man den Durchschnitt bilden soll, und insbesondere die Annahme, daß etwa jedes Problem der Größe N gleichwahrscheinlich ist, ist in der Praxis oft nicht gerechtfertigt. Hinzu kommt, daß eine Average-case-Analyse häufig technisch schwieriger durchzuführen ist als etwa eine Worst-case-Analyse…“
(Quelle: „Algorithmen und Datenstrukturen“, T.Ottmann/P.Widmayer)
Noch was, was allerdings klar sein duerfte und auch nur selten zutrifft:
Sobald du eine endliche Menge an dir bekannten Cases hast, und auch die Wahrscheinlichkeiten mit der sie auftreten kennst, kannst du die (wahrscheinlichste) Durchschnittslaufzeit ziemlich genau berechnen.
(Worstcase + Bestcase)/2 bringt dir nichts, wenn 90% der Faelle zb bei 10ms liegen und 5% bei 11ms und 5% bei 2ms.
Das ergibt: (11+2)ms/2 = 6.5ms
Unter Beachtung der Wahrscheinlichkeiten ergibt sich alerdings:
( (0.9*10)+(0.05*11)+(0.05*2) )ms ≈ 9.55 ms (geschaetzt)
Das dieses Ergebnis mehr Sinn macht ist hier wohl ziemlich deutlich.
Wenn dir die Wahrschienlichkeiten und die eizelnen Faelle nicht bekannt sind, hillft oft nur schaetzen (zumindest den Ingenieuren 
)!
–
Gruss
Dirk
http://www.phpmybackuppro.net/mozilla_search_plugins/
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]