Fallstudie - Sortieren / Präzisierung von Berechnungskomplexität
Worum geht es hier?
Sortiervorgänge kommen in der Praxis oft vor. Viele Softwarewerkzeuge bieten eine Sortierfunktion
an, die auf intelligenten
Sortieralgorithmen beruht.
Im Kapitel Sortieren steht die Entwicklung
von Sortierverfahren im Vordergrund. In diesem Kapitel wird gezeigt, dass es eine Vielzahl an Möglichkeiten gibt, Sortiervorgänge
systematisch zu konzipieren.
Bei der Bewertung der verschiedenen Sortierverfahren spielt
die Berechnungskomplexität eine wesentliche Rolle. Wir werden in diesem Kapitel die Komplexität von Sortieralgorithmen
und auch vom Sortierproblem selbst genauer analysieren und dabei die zur Beschreibung
der Zusammenhänge wichtigsten Fachkonzepte einführen.
ist
Hier lernst du ...
- ... wie man das Laufzeitverhalten von Programmen experimentell bestimmt.
- ... warum man versucht, das Laufzeitverhalten von Algorithmen mathematisch zu beschreiben.
- ... wie man Laufzeitverhalten mit Kostenfunktionen modelliert.
- ... wie man Kostenanalysen durchführt.
- ... warum man das asymptotische Wachstumsverhalten von Kostenfunktionen betrachtet.
- ... wie man Wachstumsverhalten vergleicht und klassifiziert.
- ... wie man die Komplexität von Problemen abschätzt.
