Preferred labels

en
  • complexity theory
de
  • Komplexitätstheorie

Alternative labels

en
  • computational complexity
  • computational complexity theory
de

Assigned collections

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)

Notations

Related terms

Concept mappings

Close Matches

Exact Matches

Related Matches

Broader Matches

Narrower Matches

Change notes

Editorial notes

Examples

History notes

Scope notes