Algorithmen und Datenstrukturen - 02 Sortieren - SS 24 - PDF

Algorithmen und Datenstrukturen 21.PMarc Fischlin, SS 2024 02...

Algorithmen und Datenstrukturen 21.PMarc Fischlin, SS 2024 02 Sortieren Folien beruhen auf gemeinsamer Veranstaltung mit Christian Janson aus dem SS 2020 13. Oktober 2010 | Dr.Marc Fischlin | Kryptosicherheit | 1  Das Sortierproblem Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 2 Sortierproblem in der Praxis Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 3 Sortierproblem Gegeben: Folge von Objekten Gesucht: Sortierung der Objekte (gemäß ausgewiesenen Schlüsselwerts) Schlüssel(wert) Wert, nach dem Objekt sortiert wird „Satellitendaten“ Steuer-ID Name Objekt Adresse Bankverbindung Beispiel … Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 4 Schlüsselproblem Schlüssel(werte) müssen nicht eindeutig sein, aber müssen „sortierbar“ sein Schlüssel(wert) Wert, nach dem Objekt sortiert wird „Satellitendaten“ Annahme im Folgenden: Es gibt eine totale Ordnung Objekt ≤ auf der Menge 𝑀 aller möglichen Schlüsselwerte Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 5  Exkurs Totale Ordnung Beispiel: lexikographische Ordnung auf Strings Sei 𝑀 eine nicht leere Menge und ≤ ⊆ 𝑀 × 𝑀 eine binäre Relation auf 𝑀 Die Relation ≤ auf 𝑀 ist genau dann eine totale Ordnung, wenn gilt: Reflexivität: ∀𝑥 ∈ 𝑀: 𝑥 ≤ 𝑥 Transitivität: ∀𝑥, 𝑦, 𝑧 ∈ 𝑀: 𝑥 ≤ 𝑦 ∧ 𝑦 ≤ 𝑧 ⇒ 𝑥 ≤ 𝑧 Antisymmetrie: ∀𝑥, 𝑦 ∈ 𝑀: 𝑥 ≤ 𝑦 ∧ 𝑦 ≤ 𝑥 ⇒ 𝑥 = 𝑦 (ohne Totalität: Totalität: ∀𝑥, 𝑦 ∈ 𝑀: 𝑥 ≤ 𝑦 ∨ 𝑦 ≤ 𝑥 partielle Ordnung) Bemerkung: Totale Ordnung ≤ impliziert Relation > durch 𝑥 > 𝑦: ⇔ 𝑥 ≰ 𝑦 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 6 Darstellung in diesem Abschnitt Wir betrachten nur Schlüssel(werte) ohne Satellitendaten, in Beispielen meistens durch Zahlen gegeben Eingabe der Objekte bzw. Schlüsselwerte in Form eines Arrays A: 0 1 2 3 4 5 6 7 8 A 53 12 17 44 33 25 17 4 76 Lese-/Schreibzugriff per Index in konstanter Zeit: y=A weist y den Wert 17 zu A=99 überschreibt 33 mit 99 A.length beschreibt (fixe) Länge des Arrays, im Beispiel 9 A[i…j] beschreibt Teil-Array von Index i bis j, 0=key DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; Beispiel: FOR-Schleife i=1 2 key=12 3 j=0 WHILE-Schleife j=0 A[j]=53 > key=12 7 53 12 53 12 17 87 1.Fall: 6 j=-1 5 linker Rand erreicht Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 11 Beispiel: Insertion Sort (II) insertionSort(A) 1 FOR i=1 TO A.length-1 DO // insert A[i] in pre-sorted sequence A[0..i-1] 2 key=A[i]; 3 j=i-1; // search for insertion point backwards 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; Beispiel: i=2 FOR-Schleife i=1 2 key=17 3 j=1 WHILE-Schleife j=1 A[j]=53 > key=17 53 12 53 53 17 87 2.Fall: 6 j=0 5 Einfügeposition erreicht Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 12 Beispiel: Insertion Sort (III) insertionSort(A) 1 FOR i=1 TO A.length-1 DO // insert A[i] in pre-sorted sequence A[0..i-1] 2 key=A[i]; 3 j=i-1; // search for insertion point backwards 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; Beispiel: i=2 FOR-Schleife i=1 2 key=17 3 j=1 j=1 WHILE-Schleife j=0 A[j]=12 < key=17 53 12 17 53 53 17 87 7 2.Fall: 6 j=0 Einfügeposition erreicht Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 13 Beispiel: Insertion Sort (IV) insertionSort(A) 1 FOR i=1 TO A.length-1 DO // insert A[i] in pre-sorted sequence A[0..i-1] 2 key=A[i]; 3 j=i-1; // search for insertion point backwards 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; Beispiel: i=2 i=1 FOR-Schleife i=3 2 key=87 3 j=2 j=1 j=2 WHILE-Schleife j=0 A[j]=53 < key=87 53 12 17 53 53 17 87 7 3.Fall: Element bleibt Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 14 Terminierung insertionSort(A) 1 FOR i=1 TO A.length-1 DO // insert A[i] in pre-sorted sequence A[0..i-1] 2 key=A[i]; 3 j=i-1; // search for insertion point backwards 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; Jede Ausführung der WHILE-Schleife erniedrigt jkey DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; Schleifeninvariante (der FOR-Schleife): Bei jedem Eintritt für Zählerwert i (und nach letzter Ausführung) entsprechen die aktuellen Einträge in A,…,A[i-1] den sortierten ursprünglichen Eingabewerten a,…,a[i-1]. Ferner gilt A[i]=a[i],…, A[n-1]=a[n-1]. Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 16 Korrektheit (II) Beweis per Induktion: Induktionsbasis i=1: Beim ersten Eintritt ist A=a und „sortiert“. Ferner gilt noch A=a,…,A[n-1]=a[n-1]. Bei jedem Eintritt für Zählerwert i (und nach letzter Ausführung) entsprechen die aktuellen Einträge in A,…,A[i-1] den sortierten ursprünglichen Eingabewerten a,…,a[i-1]. Ferner gilt A[i]=a[i],…, A[n-1]=a[n-1]. Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 17 Korrektheit (III) Beweis per Induktion: Induktionsschritt von i-1 auf i: Vor der (i-1)–ten Ausführung galt Schleifeninvariante nach Voraussetzung. Inbesondere war A,…,A[i-2] sortierte Version von a,…,a[i-2] und A[i-1]=a[i-1],…,A[n-1]=a[n-1] Durch die WHILE-Schleife wurde A[i-1]=a[i-1] nach links einsortiert und größere Elemente von A,…,A[i-2] um jeweils eine Position nach rechts verschoben. Elemente A[i],…,A[n-1] wurden nicht geändert Also gilt Invariante auch für i Bei jedem Eintritt für Zählerwert i (und nach letzter Ausführung) entsprechen die aktuellen Einträge in A,…,A[i-1] den sortierten ursprünglichen Eingabewerten a,…,a[i-1]. Ferner gilt A[i]=a[i],…, A[n-1]=a[n-1]. Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 18 Korrektheit (IV) Aus Schleifeninvariante folgt für letzte Ausführung (also quasi vor gedanklichem Eintritt der Schleife für i=n): A,…,A[n-1] ist sortierte Version von a,…,a[n-1] und somit am Ende das Array sortiert Bei jedem Eintritt für Zählerwert i (und nach letzter Ausführung) entsprechen die aktuellen Einträge in A,…,A[i-1] den sortierten ursprünglichen Eingabewerten a,…,a[i-1]. Ferner gilt A[i]=a[i],…, A[n-1]=a[n-1]. Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 19  Wozu brauchen Sie (intuitiv) beim Sortieren die vier Eigenschaften einer totalen Ordnung? Überlegen Sie sich, dass Insertion Sort stabil ist, d.h. die Reihenfolge von Objekten mit gleichem Schlüssel bleibt erhalten. Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 20  Laufzeitanalysen: O-Notation Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 21 Laufzeitanalyse Wieviel Schritte macht Algorithmus in Abhängigkeit von der Eingabekomplexität? meistens: schlechtester Fall über fasst alle Eingaben alle Eingaben gleicher Komplexität ähnlicher Komplexität zusammen (Worst-Case-)Laufzeit Beispiel: 𝑛 Anzahl zu 𝑇(𝑛) = max { Anzahl Schritte für x } sortierender Zahlen Maximum über alle Eingaben (man könnte auch zusätzlich x der Komplexität 𝑛 Größe der Zahlen betrachten; wird aber meist von Anzahl dominiert) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 22  𝑛 Anzahl zu Laufzeitanalyse Insertion Sort (I) sortierender Elemente Zeile Aufwand Anzahl insertionSort(A) 1 FOR i=1 TO A.length-1 DO 1 c1 𝑛 // insert A[i] in pre-sorted sequence A[0..i-1] 2 c2 𝑛−1 2 key=A[i]; 3 c3 𝑛−1 3 j=i-1; // search for insertion point backwards 4 c4 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right5 c5 6 j=j-1; 6 c6 7 A[j+1]=key; 7 c7 𝑛−1 Analysiere, wie oft jede Zeile maximal ausgeführt wird Jede Zeile 𝑖 hat Aufwand 𝑐𝑖 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 23  𝑛 Anzahl zu Laufzeitanalyse Insertion Sort (II) sortierender Elemente Zeile Aufwand Anzahl insertionSort(A) 1 FOR i=1 TO A.length-1 DO 1 c1 𝑛 // insert A[i] in pre-sorted sequence A[0..i-1] 2 c2 𝑛−1 2 key=A[i]; 3 c3 𝑛−1 3 j=i-1; // search for insertion point backwards 4 c4 Z5+𝑛 − 1 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right5 c5 𝑛(𝑛 − 1)Τ2 6 j=j-1; 6 c6 𝑛(𝑛 − 1)Τ2 7 A[j+1]=key; 7 c7 𝑛−1 Zeilen 4, 5 und 6 im schlimmsten Fall bis j=-1 also jeweils i-mal. Insgesamt: Analysiere, wie oft jede Zeile 𝑛−1 maximal ausgeführt wird 𝑛(𝑛 − 1) ෍𝑖 = 2 Jede Zeile 𝑖 hat 𝑖=1 Aufwand 𝑐𝑖 (Zeile 4 jeweils einmal mehr bis Abbruch) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 24  𝑛 Anzahl zu Laufzeitanalyse Insertion Sort (III) sortierender Elemente Zeile Aufwand Anzahl insertionSort(A) 1 FOR i=1 TO A.length-1 DO 1 c1 𝑛 // insert A[i] in pre-sorted sequence A[0..i-1] 2 c2 𝑛−1 2 key=A[i]; 3 c3 𝑛−1 3 j=i-1; // search for insertion point backwards 4 c4 Z5+𝑛 − 1 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right5 c5 𝑛(𝑛 − 1)Τ2 6 j=j-1; 6 c6 𝑛(𝑛 − 1)Τ2 7 A[j+1]=key; 7 c7 𝑛−1 maximale Gesamtlaufzeit Insertion-Sort: Analysiere, wie oft jede Zeile maximal ausgeführt wird 𝑇 𝑛 = 𝑐1 ∙ 𝑛 + 𝑐2 + 𝑐3 + 𝑐4 + 𝑐7 ∙ 𝑛 − 1 +(𝑐4 + 𝑐5 + 𝑐6) ∙ 𝑛(𝑛−1) 2 Jede Zeile 𝑖 hat Aufwand 𝑐𝑖 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 25 Kosten für individuelle Schritte? Wie teuer ist z.B. Zuweisung A[j+1]=A[j] in Zeile 5, also was ist 𝑐5? Hängt stark von Berechnungsmodell ab (in dem Pseudocode-Algorithmus umgesetzt wird)… CPU Quelle: ke.tu-darmstadt.de Quelle: de.wikipedia.org/wiki/Turingmaschine Schaltkreis RAM Turingmaschine nehmen üblicherweise an, dass elementare Operationen (Zuweisung, Vergleich,…) in einem Schritt möglich → 𝒄𝟓 = 𝟏 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 26 Asymptotische Vereinfachung (I) Zeit 𝑇(𝑛) Gesamtlaufzeit Insertion-Sort (mit 𝑐𝑖 = 1): 𝐷(𝑛) 𝑇 𝑛 = 𝑛 + 4 ∙ 𝑛 − 1 + 3 ∙ 𝑛(𝑛−1)2 Zum Vergleich (nur dominanter Term) : 𝐷(𝑛) = 3 ∙ 𝑛(𝑛−1) 2 𝑛 𝑇(𝑛) 𝐷(𝑛) relativer Fehler (𝑻 𝒏 − 𝑫 𝒏 )Τ𝑻(𝒏) 100 15.346 14.850 3,2321 % 1.000 1.503.496 1.498.500 0,3323 % 10.000 150.034.996 149.985.000 0,0333 % 100.000 15.000.349.996 14.999.850.000 0,0033 % 1.000.000 150.000.034.999.996 1.499.998.500.000 0,0003 % Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 27 Asymptotische Vereinfachung (II) Weiter Vereinfachung (nur abhängiger Term) : 𝐴(𝑛) = 𝑛(𝑛−1) 2 Zum Vergleich (nur dominanter Term) : 𝐷(𝑛) = 3 ∙ 𝑛(𝑛−1) 2 Konstante ändert sich „schnell“ durch Fortschritte in Rechenleistung Konstante hängt stark vom Berechnungsmodell ab Beispiel Moore‘s Law (bis ca. 2000): Verdoppelung der Transistoren etwa alle 1,5 Jahre Quelle: de.wikipedia.org/wiki/Mooresches_Gesetz Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 28  Paul Bachmann 𝚯-Notation / Landau-Symbole Edmund Landau ca. 1900 Funktionen 𝑓, 𝑔: ℕ ⟶ ℝ>0 Eingabekomplexität Laufzeit Θ 𝑔 = 𝑓 ∶ ∃ 𝑐1 , 𝑐2 ∈ ℝ>0 , 𝑛0 ∈ ℕ, ∀𝑛 ≥ 𝑛0 , 0 ≤ 𝑐1 𝑔(𝑛) ≤ 𝑓(𝑛) ≤ 𝑐2 𝑔(𝑛) Positive Konstanten 𝑓(𝑛) wird von 𝑐1 𝑔(𝑛) und 𝑐2 𝑔(𝑛) für hinreichend große 𝑛 eingeschlossen Funktion 𝑓 Für alle 𝑛 größer gleich 𝑛0 Schreibweise: 𝑓 ∈ Θ 𝑔 , manchmal auch 𝑓 = Θ 𝑔 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 29 Veranschaulichung 𝚯-Notation Quelle: Corman et al. Introduction to Algorithms 𝑛 ≥ 𝑛0 : 𝑐1 𝑔(𝑛) ≤ 𝑓(𝑛) 𝑐2 𝑔(𝑛) ≥ 𝑓(𝑛) 𝑔(𝑛) ist eine asymptotisch scharfe Schranke von 𝑓(𝑛) Θ-Notation beschränkt eine Funktion asymptotisch von oben und unten Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 30 Beispiel: Laufzeit Insertion Sort 𝐢𝐧 𝚯-Notation (I) 𝑇 𝑛 =𝑛+4∙ 𝑛−1 +3∙𝑛 𝑛−1 2 = Θ(𝑛2 ) Für untere Schranke wähle 𝑐1 = 32 und 𝑛0 = 2: 𝑇 𝑛 ≥ 5∙ 𝑛−1 + 32 ∙ 𝑛2 − 32 ∙ 𝑛 7 ≥ 2 ∙𝑛−5 + 32 ∙ 𝑛2 3 ≥ 2 ∙ 𝑛2 für 𝑛 ≥ 2 Θ 𝑔 = 𝑓 ∶ ∃ 𝑐1 , 𝑐2 ∈ ℝ>0 , 𝑛0 ∈ ℕ, ∀𝑛 ≥ 𝑛0 , 0 ≤ 𝑐1 𝑔(𝑛) ≤ 𝑓(𝑛) ≤ 𝑐2 𝑔(𝑛) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 31 Beispiel: Laufzeit Insertion Sort 𝐢𝐧 𝚯-Notation (II) 𝑛 𝑛−1 für 𝑐1 = 32, 𝑇 𝑛 =𝑛+4∙ 𝑛−1 +3∙ 2 = Θ(𝑛2 ) 𝑐2 = 7, 𝑛0 = 2 Für obere Schranke wähle 𝑐2 = 7 und das bereits fixierte 𝑛0 = 2: 𝑇 𝑛 ≤𝑛+ 4∙𝑛 + 2 ∙ 𝑛(𝑛 − 1) ≤ 5∙𝑛 + 2 ∙ 𝑛2 ≤ 5 ∙ 𝑛2 + 2 ∙ 𝑛2 ≤ 7 ∙ 𝑛2 Θ 𝑔 = 𝑓 ∶ ∃ 𝑐1 , 𝑐2 ∈ ℝ>0 , 𝑛0 ∈ ℕ, ∀𝑛 ≥ 𝑛0 , 0 ≤ 𝑐1 𝑔(𝑛) ≤ 𝑓(𝑛) ≤ 𝑐2 𝑔(𝑛) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 32 𝚶-Notation Obere asymptotische Schranke Ο 𝑔 = 𝑓 ∶ ∃ 𝑐 ∈ ℝ>0 , 𝑛0 ∈ ℕ, ∀𝑛 ≥ 𝑛0 , 0 ≤ 𝑓(𝑛) ≤ 𝑐𝑔(𝑛) Positive Konstanten 𝑓(𝑛) wird von 𝑐𝑔 𝑛 für hinreichend große 𝑛 Funktion 𝑓 beschränkt Für alle 𝑛 größer gleich 𝑛0 Sprechweise: 𝑓 wächst höchstens so schnell wie 𝑔 Schreibweise: 𝑓 = Ο 𝑔 oder auch 𝑓𝜖 Ο 𝑔 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 33 Veranschaulichung der 𝚶-Notation Quelle: Corman et al. Introduction to Algorithms 𝑛 ≥ 𝑛0 : 0 ≤ 𝑓(𝑛) ≤ 𝑐𝑔(𝑛) Beachte: Θ 𝑔(𝑛) ⊆ Ο 𝑔(𝑛) und somit 𝑓 𝑛 =Θ 𝑔 ⟹𝑓 𝑛 =Ο 𝑔 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 34 𝚶-Notation: Rechenregeln Konstanten: 𝑓 𝑛 = 𝑎 mit 𝑎 ∈ ℝ>0 konstant. Dann 𝑓 𝑛 = Ο 1 Skalare Multiplikation: 𝑓 = Ο 𝑔 und 𝑎 ∈ ℝ>0. Dann 𝑎 ⋅ 𝑓 = Ο 𝑔 Addition: 𝑓1 = Ο 𝑔1 und 𝑓2 = Ο 𝑔2. Dann 𝑓1 + 𝑓2 = Ο max 𝑔1 , 𝑔2 punktweise Multiplikation: 𝑓1 = Ο 𝑔1 und 𝑓2 = Ο 𝑔2. Dann 𝑓1 ⋅ 𝑓2 = Ο 𝑔1 ⋅ 𝑔2 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 35 Ω-Notation Untere asymptotische Schranke Ω 𝑔 = 𝑓 ∶ ∃ 𝑐 ∈ ℝ>0 , 𝑛0 ∈ ℕ, ∀𝑛 ≥ 𝑛0 , 0 ≤ 𝑐𝑔(𝑛) ≤ 𝑓(𝑛) Positive Konstanten 𝑓(𝑛) wird von 𝑐𝑔 𝑛 für hinreichend große 𝑛 Funktion 𝑓 unten beschränkt Für alle 𝑛 größer gleich 𝑛0 Sprechweise: 𝑓 wächst mindestens so schnell wie 𝑔 Schreibweise: 𝑓 = Ω 𝑔 oder auch 𝑓ϵ Ω 𝑔 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 36 Veranschaulichung der Ω-Notation Quelle: Corman et al. Introduction to Algorithms 𝑛 ≥ 𝑛0 : 0 ≤ 𝑐𝑔(𝑛) ≤ 𝑓(𝑛) Beachte: Θ 𝑔(𝑛) ⊆ Ω 𝑔(𝑛) und somit 𝑓 𝑛 =Θ 𝑔 ⟹𝑓 𝑛 =Ω 𝑔 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 37  Überlegen Sie sich die Rechenregeln für Ω analog zu denen für die 𝑂-Notation. Überlegen Sie sich, dass gilt: 𝑂 𝑛 ⊆ 𝑂 𝑛2 ⊆ 𝑂 𝑛3 ⊆ 𝑂 𝑛4 ⊆ 𝑂 𝑛5 ⊆ … und Ω 𝑛 ⊇ Ω 𝑛2 ⊇ Ω 𝑛3 ⊇ Ω 𝑛4 ⊇ Ω 𝑛5 ⊇… und dass die Inklusionen jeweils strikt sind Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 38 Zusammenhang 𝑶, Ω und 𝚯 Für beliebige 𝑓 𝑛 , 𝑔 𝑛 : ℕ ⟶ ℝ>0 gilt: 𝑓 𝑛 = Θ(𝑔 𝑛 ) genau dann, wenn 𝑓 𝑛 = Ο(𝑔 𝑛 ) und 𝑓 𝑛 = Ω(𝑔 𝑛 ) Beachte: Ω 𝑔 , 𝑂 𝑔 sind nur untere bzw. obere Schranken: Beispiel: 𝑓(𝑛) = Θ 𝑛3 , also auch: 𝑓 𝑛 = 𝑂 𝑛5 , da Θ 𝑛3 ⊆ 𝑂 𝑛3 ⊆ 𝑂 𝑛5 𝑓 𝑛 = Ω(𝑛), da Θ 𝑛3 ⊆ Ω 𝑛3 ⊆ Ω(𝑛) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 39 Anwendung O-Notation (I) 𝑓 = 𝑂(𝑔) übliche Schreibweise, sollte aber gelesen werden als 𝑓 ∈ 𝑂(𝑔) Allgemein besser immer als Mengen auffassen und von links nach rechts lesen (mit ∈, ⊆): 5 ∙ 𝑛2 + 𝑛4 = 𝑂 𝑛2 + 𝑛4 = 𝑂 𝑛4 = 𝑂(𝑛5 ) ∈ ⊆ ⊆ als Menge 𝑓 𝑛 + 𝑛4 = { 𝑓(𝑛) + 𝑛4 } nicht: 𝑶 𝒏𝟒 = 𝑶 𝒏𝟓 , und damit auch 𝑶 𝒏𝟓 = 𝑶 𝒏𝟒 wird mit Mengenschreibweise klarer: 𝐴 ⊆ 𝐵 bedeutet allgemein nicht auch 𝐵 ⊆ 𝐴 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 40 Anwendung O-Notation (II) Ungleichungen mit ≤ sollten nur mit 𝑂 verwendet werden, Ungleichungen mit ≥ sollten nur mit Ω verwendet werden. 5 ∙ 𝑛2 + 𝑛4 ≤ 6 ∙ 𝑛4 = 𝑂 𝑛4 es gibt 𝑐, 𝑛0 und Funktion 𝑓(𝑛) mit 6 ∙ 𝑛4 ≤ 𝑐 ∙ 𝑓(𝑛) obere Schranke vs. untere Schranke nicht: 𝟓 ∙ 𝒏𝟐 + 𝒏𝟒 ≤ 𝟔 ∙ 𝒏𝟒 = 𝜴 𝒏𝟒 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 41 𝑶, Ω und 𝚯 bei Insertion Sort (I) insertionSort(A) 1 FOR i=1 TO A.length-1 DO // insert A[i] in pre-sorted sequence A[0..i-1] 2 key=A[i]; 3 j=i-1; // search for insertion point backwards 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; Algorithmus macht maximal 𝑇 𝑛 viele Schritte und 𝑇 𝑛 = Θ(𝑛2 ) Also Laufzeit Insertion Sort = Θ(𝑛2 ) ? korrekte Anwendung: Laufzeit ≤ 𝑇 𝑛 = 𝑂(𝑛2 ) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 42 𝑶, Ω und 𝚯 bei Insertion Sort (II) insertionSort(A) 1 FOR i=1 TO A.length-1 DO // insert A[i] in pre-sorted sequence A[0..i-1] 2 key=A[i]; 3 j=i-1; // search for insertion point backwards 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; zur Erinnerung: (Worst-Case-)Laufzeit 𝑇(𝑛) = max { Anzahl Schritte für x } Für untere Schranke muss man „nur“ eine schlechte bzw. die schlechteste Eingabe x finden Dann gilt 𝑇(𝑛) ≥ Anzahl Schritte für schlechtes x Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 43  𝑶, Ω und 𝚯 bei Insertion Sort (III) Insertion Sort hat quadratische insertionSort(A) Laufzeit Θ(𝑛2 ) 1 FOR i=1 TO A.length-1 DO // insert A[i] in pre-sorted sequence A[0..i-1] 2 key=A[i]; 3 j=i-1; // search for insertion point backwards 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; „Schlechte“ Eingabe: A 𝑛 𝑛−1 𝑛−2 … … 2 1 Jede WHILE-Schleifenausführung für 𝑖 = 1, … , 𝑛 − 1 macht jeweils 𝑖 Iterationen Insgesamt macht Algorithmus für A also σ𝑛−1 𝑖=1 𝑖 = 𝑛(𝑛−1) 2 = Ω(𝑛2 ) Schritte Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 44 „Gute“ Eingaben für Insertion Sort? insertionSort(A) 1 FOR i=1 TO A.length-1 DO // insert A[i] in pre-sorted sequence A[0..i-1] 2 key=A[i]; 3 j=i-1; // search for insertion point backwards 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; „gute“ Eingaben bereits vorsortiert, extremes Beispiel: A 1 2 3 … … 𝑛−2 𝑛−1 WHILE-Schleife wird für dieses A nie ausgeführt Insgesamt macht Algorithmus für dieses A also Θ(𝑛) Schritte Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 45 Laufzeit Insertion Sort (I) „guter“ Fall „schlechter“ Fall (fast vorsortiertes Array) (invertiertes, vorsortiertes Array) Quelle: https://web.archive.org/web/20150302064244/http://www.sorting-algorithms.com/insertion-sort Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 46 Laufzeit Insertion Sort (II) „guter“ Fall „schlechter“ Fall (fast vorsortiertes Array) (invertiertes, vorsortiertes Array) Quelle: https://web.archive.org/web/20150302064244/http://www.sorting-algorithms.com/insertion-sort Insertion Sort hat Wort-Case-Laufzeiten: auch wenn für manche Eingaben schneller, gilt: quadratische Laufzeit Θ(𝑛2 ) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 47 Komplexitätsklassen 𝑛 ist die Länge der Eingabe (z.B. Arraylänge, Länge des Strings) Klasse Bezeichnung Beispiel Θ(1) Konstant Einzeloperation Θ(log 𝑛) Logarithmisch Binäre Suche Θ(𝑛) Linear Sequentielle Suche Θ(𝑛 log 𝑛) Quasilinear Sortieren eines Arrays Θ(𝑛2 ) Quadratisch Matrixaddition Θ(𝑛3 ) Kubisch Matrixmultiplikation Θ(𝑛𝑘 ) Polynomiell Θ(2𝑛 ) Exponentiell Travelling-Salesperson* Θ(𝑛!) Faktoriell Permutationen *wenn der Algorithmus geschickt implementiert ist Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 48 𝝄-Notation und ω-Notation nicht asymptotisch scharfe Schranken 𝜊 𝑔 = 𝑓 ∶ ∀ 𝑐 ∈ ℝ>0 , ∃𝑛0 ∈ ℕ, ∀𝑛 ≥ 𝑛0 , 0 ≤ 𝑓 𝑛 < 𝑐𝑔(𝑛) Gilt für alle Konstanten 𝑐 > 0, in Ο-Notation für eine Konstante 𝑐 > 0 Beispiel: 2𝑛 = 𝜊 𝑛2 und 2𝑛2 ≠ 𝜊 𝑛2 𝜔 𝑔 = 𝑓 ∶ ∀𝑐 ∈ ℝ>0 , ∃𝑛0 ∈ ℕ, ∀𝑛 ≥ 𝑛0 , 0 ≤ 𝑐𝑔 𝑛 < 𝑓(𝑛) 2 𝑛2ൗ Beispiel: 𝑛 ൗ2 = ω 𝑛 und 2 ≠ 𝜔 𝑛2 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 49  Was macht der folgende Sortier-Algorithmus Bubble-Sort? bubbleSort(A) 1 FOR i=A.length-1 DOWNTO 0 DO 2 FOR j=0 TO i-1 DO 3 IF A[j]>A[j+1] THEN SWAP(A[j],A[j+1]); //temp=A[j+1]; A[j+1]=A[j]; A[j]=temp; Welche Laufzeit hat der Algorithmus? Wie verhält er sich im Vergleich zu Insertion Sort? Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 50  Merge Sort Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 51  Entwurfsmethoden Idee Divide & Conquer (& Combine) → Abschnitt 7 Teile Liste in Hälften, sortiere (rekursiv) Hälften, sortiere wieder zusammen (Teil-)Sortierung 53 12 17 44 können im Array A[0…3] selbst erfolgen 53 12 17 44 A[0…1], A[2…3] 53 12 17 44 A,A,A,A 12 53 17 44 A[0…1], A[2…3] linke & rechte Grenze A[0…3] 12 17 44 53 beschreiben Teilliste Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 52 Algorithmus: Merge Sort Wir sortieren im Array A zwischen Position left (links) und right (rechts) mergeSort(A,left,right) //initial left=0,right=A.length-1 1 IF left