Algorithmen in einer Kurzfassung, 2.

Anhang A. Benchmarking

Jeder Algorithmus in diesem Buch wird von Daten über seine Leistung begleitet. Da es wichtig ist, die richtigen Benchmarks zu verwenden, um eine genaue Leistung zu erhalten, stellen wir in diesem Anhang unsere Infrastruktur zur Bewertung der Algorithmenleistung vor. Dies soll auch dazu beitragen, Fragen oder Zweifel an der Gültigkeit unseres Ansatzes zu klären. Wir versuchen zu erklären, wie die empirischen Daten genau berechnet werden, damit du überprüfen kannst, ob die Ergebnisse korrekt sind, und damit du verstehst, wo die Annahmen in dem Kontext, in dem der Algorithmus eingesetzt werden soll, angemessen sind.

Es gibt zahlreiche Methoden, mit denen Algorithmen analysiert werden können. In Kapitel 2 wurden die Konzepte der Worst-Case- und Average-Case-Analyse theoretisch und formal behandelt. Diese theoretischen Ergebnisse können in einigen Fällen empirisch ausgewertet werden, aber nicht in allen. Betrachte zum Beispiel die Bewertung der Leistung eines Algorithmus, der 20 Zahlen sortiert. Es gibt 2,^43*1018 Permutationen dieser 20 Zahlen, und wir können nicht einfach jede dieser Permutationen erschöpfend auswerten, um den Durchschnittsfall zu berechnen. Außerdem können wir den Durchschnitt nicht berechnen, indem wir die Zeit für das Sortieren all dieser Permutationen messen. Wir müssen uns auf statistische Maße verlassen, um sicherzustellen, dass wir die erwartete Leistungszeit des Algorithmus richtig berechnet haben.

Statistische Grundlage

Dieses Kapitel ...