Begriff
Komplexitätstheorie
Warum wichtig?
Dieser Begriff ist ein Knoten im SengakujiWorks-Wissensnetz. Nutze Level 0 für die erste Einordnung, Level 1 für Praxis, Level 2 für technische Struktur und Level 3 für Grenzen, Fallstricke und Expertenkontext.
Komplexitätstheorie fragt, wie aufwendig ein Problem zu lösen ist. Es geht nicht nur darum, ob ein Algorithmus funktioniert, sondern wie viel Zeit oder Speicher er braucht.
Merksatz: Komplexitätstheorie bewertet die Kosten des Rechnens.
Wenn eine Suche bei 100 Einträgen schnell ist, aber bei 10 Millionen langsam wird, ist Komplexität relevant. Entwickler nutzen Big-O, um abzuschätzen, ob ein Ansatz mit wachsenden Daten noch tragfähig ist.
Die Theorie ordnet Probleme in Klassen wie P, NP oder NP-vollständig ein. Manche Probleme lassen sich effizient lösen, andere sind vermutlich grundsätzlich teuer. Reduktionen zeigen, dass ein Problem mindestens so schwer ist wie ein bekanntes Problem.
Theoretische Komplexität ist nicht dasselbe wie reale Performance. Konstanten, Caches, Datenformate und Netzwerkkosten zählen ebenfalls. Trotzdem schützt die Theorie vor Designs, die bei Wachstum zwangsläufig scheitern.
Quick-Check
Was bewertet Komplexitätstheorie?
Den Zeit- und Speicheraufwand von Problemen und Algorithmen.Warum ist Big-O nützlich?
Es zeigt, wie ein Algorithmus mit der Eingabegröße wächst.Was ist eine praktische Grenze?
Realwelt-Performance hängt auch von Hardware, Datenlayout und Konstanten ab.