Komplexitätstheorie Konzept
Bevorzugte Labels
en
- complexity theory
de
- Komplexitätstheorie
Alternative Labels
en
- computational complexity
- computational complexity theory
de
Zugewiesene Kollektionen
Allgemeinere Begriffe
Spezifischere Begriffe
Definition
de
Teilgebiet der theoretischen Informatik, das sich mit der Frage beschäftigt, wie sich Algorithmen für sehr große Eingaben verhalten. Hierzu werden Algorithmen anhand ihres Speicherplatzbedarfs und Zeitverbrauchs in verschiedene Komplexitätsklassen eingeteilt, die Rückschlüsse auf das asymptotische Wachstum der untersuchten Parameter zulassen. Im Gegensatz zur Berechenbarkeitstheorie, die Fragen nach der puren Existenz von Berechnungsverfahren beantwortet, stellt die Komplexitätstheorie die praktische Verwertbarkeit von Algorithmen in den Vordergrund. (Hoffmann, Dirk W.: Theoretische Informatik. 2., aktualisierte Aufl. München : Hanser, 2011)