Eine Charakterisierung der Wachstumsrate der Laufzeit eines Algorithmus als Funktion der Eingabegröße, typischerweise asymptotisch ausgedrückt (z. B. Big O), um Skalierbarkeit zu vergleichen.

Prinzip

Ressourcennutzung wird als Funktion der Eingabegröße abstrahiert, sodass dominante Terme das asymptotische Verhalten bestimmen und Vergleiche unabhängig von maschinenspezifischen Konstanten ermöglichen.

Demonstration

Quicksort hat im Durchschnitt die Laufzeitkomplexität O(n log n), während Insertionsort im schlimmsten Fall O(n^2) hat; für große n skaliert Quicksort besser trotz Konstanteffekten.

Fehlanwendung

Big O als exakte Laufzeit zu verwenden, den Unterschied zwischen Durchschnitts‑ und Worst‑Case zu ignorieren oder Algorithmen allein nach asymptotischer Klasse zu wählen, wenn Konstanten und Eingabeverteilungen relevant sind.

Konsequenz

Richtige Anwendung informiert die Auswahl von Algorithmen, prognostiziert Performance‑Trends für große Eingaben und beeinflusst komplexitätstheoretische Trade‑offs in Entwurf und Optimierung.

Umkehrung

Ausschließlich auf konstante Faktoren und Mikrobenchmarks zu achten, ohne asymptotisches Wachstum zu berücksichtigen, kann schlechte Skalierung bei großen Eingaben verbergen.

Abgrenzung

Betrifft Zeit als abstrakte Ressource gemessen an der Eingabegröße; schließt implementierungsabhängige Konstanten, hardware‑spezifische Optimierungen und nicht‑zeitliche Ressourcen wie Speicher oder Energie aus (sofern nicht explizit einbezogen).

Semantische Spannung

Wird häufig mit empirischer Laufzeit oder 'Effizienz' verwechselt; zeitliche Komplexität ist eine asymptotische, modellbasierte Abstraktion, kein exaktes Leistungsmaß.

Synthese

Zeitliche algorithmische Komplexität ist die asymptotische Beschreibung, wie die Laufzeit eines Algorithmus mit der Eingabegröße wächst; sie dient der Bewertung der Skalierbarkeit und der Auswahl von Algorithmen unter idealisierten Kostenmodellen.