Alogorithmus beurteilen
-
Hallo Liebe Leute, ich hab ein verfahren zur suche entwickelt. Habe dabei folgendes Problem ich wollte gerne auf Mathematischen wege die Laufzeit meines Algorithmus beweisen. Da meine Fähigkeiten in dem punkte derzeitig beschränkt sind
hätte ich gerne mal nen kleines Beispiel wie ich ein Algorithmus beurteilen kann.
Die Best Case Analyse ist ja relativ einfach. Aber wie schaffe ich die worst and avergage Case zu ermitteln um sie mit gängigen Such Algorithmen zu vergleichen
-
Worst Case ist eigentlich ganz einfach. Einfach immer den schlechtmöglichsten Fall untersuchen (und falls nicht offensichtlich, zeigen, dass dies der schelchtmöglichste ist). Average Case ist komplizierter. Hier muss man sich ersteinmal fragen, was überhaupt die Menge aller Werte ist und über *alle* das Mittel bilden. Da dies vielfach sehr aufwändig ist, begnügt man sich insbesondere bei hässlich zu untersuchenden Algorithmen (oder Algorithmen, bei denen eine komplette Analyse zu aufwändig ist, oder wenn man nicht mathematisch sauber weiß, wie ein "durchschnittlicher Fall" aussehen soll) sehr häufig damit, dass man ein Testprogramm erstellt, dies über eine repräsentative Datenmenge laufen lässt und die Zeiten misst und anschließend diese analysiert.