DSAl

• Worst-Case-Komplexität von Algorithmen


  Laufzeit eines Algorithmus ist eine Funktion, die für jede Eingabelänge die schlechteste Laufzeit angibt
• Sequentielle Berechenbarkeitsthese: Die benötigte Laufzeit für ein Problem auf zwei unterschiedlichen sequentiellen Berechenbarkeitsmodellen unterscheidet sich nur um ein Polynom
• Random Access Machine (RAM)

  Modell für die Laufzeitanalyse, ähnlich einem normalen von Neumann-Computer, mit einfachem Speicher und Prozessor
• Grenzen des RAM-Modells: Sehr große Zahlen in Speicherzellen und konstante Ausführungszeit für Anweisungen sind unrealistisch
• RAM (Random Access Machine)

  Besteht aus:

  1 Einem Speicher aus Speicherzellen 1, 2, 3,...

  2 Jede Speicherzelle kann beliebige Zahlen speichern

  3 Der Inhalt einer Speicherzelle kann als Anweisung interpretiert werden

  4 Einem Prozessor der einfache Anweisungen ausführt

  5 Anweisungen: Logische und Arithmetische Verknüpfungen, (bedingte) Sprünge

  6 Jede Anweisung benötigt konstante Zeit
• Quicksort


  1 Wähle ein Pivotelement k aus der Menge der Elemente

  2 Teile die Menge in zwei Teilmengen: Elemente kleiner als k und Elemente größer als k

  3 Wende Quicksort rekursiv auf die beiden Teilmengen an

  4 Füge die sortierten Teilmengen zusammen
• Quicksort benötigt im Durchschnitt O(n log n) Schritte auf einer RAM
• 1. Notation


  O(f) = {g: N -> R | es gibt c > 0 und N > 0 so dass für alle n >= N gilt: |g(n)| <= c|f(n)|}

  Ω(f) = {g: N -> R | es gibt c > 0 und N > 0 so dass für alle n >= N gilt: |g(n)| >= c|f(n)|}

  Θ(f) = {g: N -> R | es gibt c1, c2 > 0 und N > 0 so dass für alle n >= N gilt: c1|f(n)| <= |g(n)| <= c2|f(n)|}
• O(f(n)) = O(g(n)) bedeutet in Wirklichkeit O(f(n)) ⊆ O(g(n))
• log(n^2 + 3n + 5) = O(log n)
• (f (n)) = O(g(n))


  Oder allgemein eine Gleichung, mit O-Notation auf der linken und rechten Seite
• In Wirklichkeit ist es O(f (n)) ⊆ O(g(n))
• Wir beweisen O(f (n)) + O(g(n)) = O(|f (n)| + |g(n)|)
• Beweis


  1. Sei ˆf (n) = O(f (n)) und ˆg(n) = O(g(n)) beliebig

  2. |ˆf (n)| ≤ c|f (n)| und |ˆg(n)| ≤ c|g(n)| für ein c und große n

  3. |ˆf (n)| + |ˆg(n)| ≤ c(|f (n)| + |g(n)|)

  4. Daraus folgt O(|f (n)|) + O(|g(n)|) = O(|f (n)| + |g(n)|)

  5. Es gilt aber O(f (n)) = O(|f (n)|) und O(g(n)) = O(|g(n)|)
• Schätze log(n2 + 3n + 5) ab

  log(n2 + 3n + 5) = 2 log(n) + log(1 + 3/n + 5/n2) = 2 log(n) + O(1/n)
• Theorem: f : N → R und g : R → R. limn→∞ f (n) = 0. g : R → R in einer Umgebung des Ursprungs k mal stetig differenzierbar. Dann gilt g(f (n)) = Σ(k-1)i=0 g(i)(0)f (n)i/i! + O(f (n)k)
• Beweis: Rk-1 = g(k)(ξ)f (n)k/k! für ein ξ ∈ [-|f (n)|, |f (n)|], falls f (n) nahe bei 0. ⇒ Rk-1 ≤ maxξ∈[-ϵ,ϵ] g(k)(ξ)f (n)k/k! für ein ϵ > 0 bis auf endlich viele n. Da g(k) stetig und [-ϵ, ϵ] kompakt ist, existiert das Maximum nach dem Satz von Weierstraß. Also gilt Rk-1 = O(f (n)k)
• Beispiele


  • 1/(1 + 1/n) = 1 + O(1/n)
  • 1/(1 + 1/n) = 1 - 1/n + O(1/n2)
  • 1/(1 + 1/n) = 1 - 1/n + 1/n2 + O(1/n3)
  • √n + 1 = √n(1 + O(1/n)) = √n + O(1/√n)
• Doppelt verkettete Listen: Zusätzlicher Listenkopf, Daten in Knoten gespeichert, Zeiger zum Vorgänger und Nachfolger, Zyklisch geschlossen
• Doppelt verkettete Listen


  • Geeignet für kleine assoziative Arrays
  • Sehr geeignet für Adjazenzlistendarstellung
• Listnode

  Klasse, die einen Knoten der doppelt verketteten Liste repräsentiert
• Methoden der Listnode-Klasse

  1. delete(): Löscht den Knoten aus der Liste

  2. copy(Listnode n): Kopiert die Daten eines Knotens in den aktuellen Knoten

  3. append(Listnode newnode): Hängt einen neuen Knoten an den aktuellen Knoten an
• Methoden der ADList-Klasse


  1. append(K k, D d): Hängt einen neuen Knoten mit Schlüssel k und Daten d an das Ende der Liste an

  2. prepend(K k, D d): Fügt einen neuen Knoten mit Schlüssel k und Daten d am Anfang der Liste ein

  3. delete(K k): Löscht den Knoten mit Schlüssel k aus der Liste

  4. find(K k): Sucht den Knoten mit Schlüssel k und gibt die Daten zurück
• Einfach verkettete Listen: Kein Zeiger auf Vorgänger, einfachere Datenstruktur, Operationen können komplizierter sein
• Einfügen eines Elements vor einen gegebenen Knoten

  Ersetzen und alten Knoten anfügen, eine gefährliche Technik
• Laufzeit von Listenoperationen

  • append(): Θ(1)
  • delete() (direktes Löschen): Θ(1)
  • delete() (über Schlüssel): Θ(n)
  • find(): Θ(n)
  • insert(): Θ(n)
• Stack


  Datenstruktur, bei der Elemente am Ende hinzugefügt und entfernt werden
• Queue


  Datenstruktur, bei der Elemente am Anfang hinzugefügt und am Ende entfernt werden
• O(f ) = {g : N → R   ∃c ∈ R + ∃N ∈ N ∀n ≥ N : |g(n)| ≤ c|f(n)|}
• Ω(f ) = { g : N → R | ∃c ∈ R + ∃N ∈ N ∀n ≥ N : |g(n)| ≥ c|f (n)| }
• Θ(f ) = { g : N → R  | ∃c1, c2 ∈ R + ∃N ∈ N ∀n ≥ N : c1|f (n)| ≤ |g(n)| ≤ c2|f (n)| .}
• • g = O(f ) ≈ g wächst langsamer als f
• g = Ω(f ) ≈ g wächst schneller als f
• g = Θ(f ) ≈ g wächst so schnell wie f
• • O(f ) = { g : N → R    lim sup n→∞ |g(n)| / |f (n)| existiert }
  • Ω(f ) ={ g : N → R    lim inf n→∞ |g(n)| / |f (n)| ̸= 0 }
  • Θ(f ) = { g : N → R    lim inf n→∞ |g(n)| |f (n)| ̸= 0 und lim sup n→∞ |g(n)| / |f (n)| existiert o Ω(f ) = n g : N → R    lim sup n→∞ |g(n)| / |f (n)| ̸= 0}
• Grenzen des RAM Modells

  • Jede Speicherzelle enthält beliebige Zahlen: Unrealistisch, wenn diese sehr groß werden
  • Jede Anweisung benötigt gleiche Zeit: Unrealistisch, wegen Caches, Sprungen ¨
  • Daumenregel: Bei n Speicherzellen, O(log n) bits verwenden.
• Eine RAM besteht aus:

  1. Einem Speicher aus Speicherzellen 1, 2, 3,. . .
  2. Jede Speicherzelle kann beliebige Zahlen speichern
  3. Der Inhalt einer Speicherzelle kann als Anweisung interpretiert werden
  4. Einem Prozessor der einfache Anweisungen ausfuhrt ¨
  5. Anweisungen: Logische und Arithmetische Verknupfungen, (bedingte) Sprünge ¨
  6. Jede Anweisung benötigt konstante Zeit
• Einfach verkettete Liste

  • Kein Zeiger auf Vorgänger
  • Einfachere Datenstruktur
  • Operationen können komplizierter sein
• public class Stack⟨D⟩ {

  private ADList⟨Object, D⟩ stack;

  private int size;

  public Stack() { stack = new ADList⟨Object, D⟩(); size = 0; }

  public boolean isempty() { return size == 0; } public D pop() {

  D x = stack.firstnode().getData(); stack.firstnode().delete();

  size−−;

  return x;

  }

  public void push(D x) { stack.prepend(null, x); size++; }

  public int size() { return size; }

  }
• public class Queue⟨D⟩ {

  private ADList⟨Object, D⟩ queue;

  private int size;

  public Queue() { queue = new ADList⟨Object, D⟩(); size = 0; }

  public boolean isempty() { return size == 0; } public D dequeue() { D x = queue.lastnode().getData(); queue.lastnode().delete();

  size−−;

  return x;

  }

  public void enqueue(D x){ queue.prepend(null, x);

  size++;

  }

  public int size() { return size; } }