complexity theory Concept
Preferred labels
en
- complexity theory
de
- Komplexitätstheorie
Alternative labels
en
- computational complexity
- computational complexity theory
de
Assigned collections
Broader terms
Narrower terms
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)