Direkt zum Inhalt

Lexikon der Mathematik: Berechnungskomplexität

auch kurz Komplexität, die Schwierigkeit eines Problems bzgl. eines vorgegebenen Komplexitätsmaßes wie z. B. der worst case Rechenzeit, average case Rechenzeit, der Schaltkreiskomplexität oder der Raumkomplexität.

Die Komplexität ist gleich einer Funktion f(n), wobei n die Eingabelänge bezeichnet, wenn es einen Algorithmus oder eine Realisierung gibt, für die die Ressourcen asymptotisch durch O(f(n)) beschränkt sind, und es keine Möglichkeit gibt, mit durch o( f(n)) beschränkten Ressourcen auszukommen.

Oftmals sind nur untere und obere Schranken für die Komplexität bekannt. Polynomielle Komplexität beschreibt eine obere Schranke für die Komplexität, die durch eine polynomiell wachsende Funktion gegeben ist. Exponentielle Komplexität beschreibt eine untere Schranke für die Komplexität, die durch eine exponentiell wachsende Funktion gegeben ist.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos