1. Teil der Vorlesung – Grundlagen der Algorithmenanalyse
Inhalt Wie beschreibt man einen Algorithmus? Wie beweist man die Korrektheit eines Algorithmus? Rechenmodell Laufzeitanalyse
InsertionSort(Array A) Eingabegröße n for j 2 to length[A] do length[A] = n key A[j] i j-1 verschiebe alle Elemente aus while i>0 and A[i]>key do A[1…j-1], die größer als key A[i+1] A[i] sind eine Stelle nach rechts i i-1 A[i+1] key Speichere key in Lücke Fragestellung Wie kann man die Laufzeit eines Algorithmus vorhersagen?
Laufzeitanalyse
Laufzeitanalyse
Laufzeit hängt ab von Größe der Eingabe (Parameter n) Art der Eingabe (Insertionsort ist schneller auf sortierten Eingaben) Analyse Parametrisiere Laufzeit als Funktion der Eingabegröße Finde obere Schranken (Garantien) an die Laufzeit
Laufzeitanalyse
Worst-Case Analyse Für jedes n definiere Laufzeit T(n) = Maximum über alle Eingaben der Größe n Garantie für jede Eingabe Standard Average-Case Analyse Für jedes n definiere Laufzeit T(n) = Durchschnitt über alle Eingaben der Größe n Hängt von Definition des Durchschnitts ab (wie sind die Eingaben verteilt)
Laufzeitanalyse
Laufzeit hängt auch ab von Hardware (Prozessor, Cache, Pipelining) Software (Betriebssystem, Programmiersprache, Compiler) Aber Analyse soll unabhängig von Hard- und Software gelten
Laufzeitanalyse
Maschinenmodell Eine Pseudocode-Instruktion braucht einen Zeitschritt Wird eine Instruktion r-mal aufgerufen, werden r Zeitschritte benötigt Formales Modell: Random Access Machines (RAM Modell) Idee Ignoriere rechnerabhängige Konstanten Betrachte Wachstum von T(n) für n „Asymptotische Analyse“
InsertionSort(Array A) Zeit: for j 2 to length[A] do n key A[j] i j-1 while i>0 and A[i]>key do A[i+1] A[i] i i-1 A[i+1] key
Laufzeitanalyse
InsertionSort(Array A) Zeit: for j 2 to length[A] do n key A[j] n-1 i j-1 while i>0 and A[i]>key do A[i+1] A[i] i i-1 A[i+1] key
Laufzeitanalyse
InsertionSort(Array A) Zeit: for j 2 to length[A] do n key A[j] n-1 i j-1 n-1 while i>0 and A[i]>key do A[i+1] A[i] i i-1 A[i+1] key
Laufzeitanalyse
InsertionSort(Array A) Zeit: for j 2 to length[A] do n key A[j] n-1 i j-1 n-1 while i>0 and A[i]>key do n-1 + S t A[i+1] A[i] i i-1 A[i+1] key t : Anzahl Wiederholungen der while-Schleife bei Laufindex j
Laufzeitanalyse j j
InsertionSort(Array A) Zeit: for j 2 to length[A] do n key A[j] n-1 i j-1 n-1 while i>0 and A[i]>key do n-1 + S t A[i+1] A[i] S t i i-1 A[i+1] key t : Anzahl Wiederholungen der while-Schleife bei Laufindex j
Laufzeitanalyse j j j
InsertionSort(Array A) Zeit: for j 2 to length[A] do n key A[j] n-1 i j-1 n-1 while i>0 and A[i]>key do n-1 + S t A[i+1] A[i] S t i i-1 S t A[i+1] key t : Anzahl Wiederholungen der while-Schleife bei Laufindex j
Laufzeitanalyse j j j j
InsertionSort(Array A) Zeit: for j 2 to length[A] do n key A[j] n-1 i j-1 n-1 while i>0 and A[i]>key do n-1 + S t A[i+1] A[i] S t i i-1 S t A[i+1] key n-1 t : Anzahl Wiederholungen der while-Schleife bei Laufindex j
Laufzeitanalyse j j j j
InsertionSort(Array A) Zeit: for j 2 to length[A] do n key A[j] n-1 i j-1 n-1 while i>0 and A[i]>key do n-1 + S t A[i+1] A[i] S t i i-1 S t A[i+1] key n-1 t : Anzahl Wiederholungen der while-Schleife bei Laufindex j
Laufzeitanalyse j j j 5n-4+3 S t j j
Laufzeitanalyse
Worst-Case Analyse t =j-1 für absteigend sortierte Eingabe (schlechtester Fall) j
Laufzeitanalyse
Worst-Case Analyse t =j-1 für absteigend sortierte Eingabe (schlechtester Fall) j
Laufzeitanalyse
Worst-Case Analyse t =j-1 für absteigend sortierte Eingabe (schlechtester Fall) Abstraktion von multiplikativen Konstanten O-Notation (gleich) j
Comments