Welche Eigenschaften interessieren uns bei Algorithmen
Korrektheit
Laufzeit
Speicherplatz
Kommunikationszeit
Güte
Warum ist es keine gute Idee, zum Bewerten von Algorithmen deren Laufzeit zu messen
Es wird durch folgendes unmöglich Algorithmen zu vergleichen
Unterschiedliche Compiler
Betreibsstem
schneller Hardware
Laufzeitumgebungen
Eingaben
verwendete Datenstruckturen
Wie vergleichen wir Algorithmen
Idealisierter Rechner mit Festen befehlen abzählbar unendliche ram,
Laufzeit Rambefehle
speicherbedarf benötigte speicherzellen
Ermittlung charakteristischer Parameter
(sortieren -> Vertauschungen & Vergleiche)
Laufzeit & Speicher ist in der Regel abhängig von der Größe der Eingabe
Laufzeit und Speicherbedarf ist abhängig von der Eingabe
Warum ist die Komplexität der Algorithmen interessant? Sind heutige Rechner
nicht füur alle Probleme ausreichend schnell?
Bei einer Laufzeit von 2^n brint ein Doppelt so schneller rechner dargestellt als gleichung 2*2^n was umgerechnet 2^n+1 ist! Mit anderen Worten in dem Fall sorgt ein Doppelt so schneller Rechner nur für eine größere eingabe von 1
Wir haben zur asymptotischen Aufwandsabschätzung die Klasse Groß-O definiert.
Geben Sie diese Definition an und erklären Sie die einzelnen Teile
Dabei betrachten wir nur Funktionen mit natürlichen Funktionswerten, also f, g : N → N, weil wir die Anzahl von Schritten oder benutzten Speicherzellen angeben. Konstante Faktoren c werden bei Aufwandsabschätzungen vernachlässigt; es wird nur das asymptotische Wachstum der Funktionen betrachtet, also das Verhalten bei großen Werten von n.
Hinweis: In der Klausur kann nat¨urlich auch nach der Definition von Groß-Omega oder Groß-Theta gefragt werden
Wird die Groß-O-Notation nur fürr die Angabe von Worst-Case-Abschätzungen genutzt? Mit Erläuterung
Nein. Es können auch obere Schranken fürr Average- oder Best-Case-Abschätzungen angegeben werden. Groß-O heißt nicht automatisch Worst-Case, es beschreibt lediglich obere Schranken.
Wie ist die Worst-Case-Laufzeitkomplexität definiert
Die Menge der zulässigen Eingaben der Länge n bezeichnen wir mit Wn, die Anzahl der Schritte von Algorithmus A für Eingabe w mit A(w).
Dann ist die Worst-Case-Komplexität definiert als
TA(n) = sup{A(w) | w ∈ Wn}
und ist eine obere Schranke fürr die maximale Anzahl der Schritte, die Algorithmus A benötigt, um Eingaben
der Größe n zu bearbeiten.
TA(n)$ ist der Maximalwert, den die Funktion A(w) annehmen kann, wenn alle möglichen Wörter w der exakten Länge n ausgewertet werden.
Eingabelänge = n
Lulässige eingabelänge = Wn
Alogirthmus = a
Alogirithmus für eingabe w = A(w)
Last changeda day ago
