Algorithmen Probleme

• Sortieren
  => Merge Sort O(n log n)

• Interval Scheduling Problem
  => Greedy Algorithmus O(n)

• Gewichtetes Intervall Sceduling Problem
  => Dynamische Programmierung Tabularization O(n log n)

• Rucksackproblem normal
  => Greedy Algorithmus O(n)

• Rucksackproblem gewichtet
  => Dynamische Programmierung Tabularization O(n log n)

• Levenshtein Distanz für Strings
  => Dynamische Programmierung 2D Tabularization $O(n\ast m)n=|s_{1|}m=|s_2|$

Graphen

• eulerisch (hat eine Eulertour)
  => Hierholzer Algrithmus O(n + m)

• Hamilton Kreis
  => NP-vollständig

• minimal aufspannender Baum
  => Algorithmus von Kruskal O(m log n)

• günstigsten Weg von einem Knoten zu einem anderen
  => Dijkstra O((m + n) log n)

• günstigster Weg in Graph mit negativen Kanten
  => Bellmann-Ford Algorithmus O(n * m)

• günstigster Weg von jedem Knoten zu jedem anderen Knoten
  => Floyd-Warshall Algorithmus O( n³ )

• Augmentierende Pfade in bipartiten Graphen
  => Breiten Suche O( n² )

• Max-Fluss Problem
  => Max Flow Problem O( m * M ) M = max Flusswert

• allgemeines Matching
  => Max-Fluss Problem

• Perfektes Matching Problem
  => Heiratssatz