Laufzeitverhalten

T(N) ist eine Funktion, die die Laufzeit eines Algorithmus für eine Eingabegröße N beschreibt. Intuitiv entspricht T(N) der Anzahl Schritte, die der Algorithmus für eine Eingabe der Größe N benötigt.

Beispiel: Bei der Suche in einem Array mit N Elementen könnte T(N) = N sein (lineare Suche) oder T(N) = log(N) (binäre Suche).

Weil die Anzahl/Art der Anweisungen von Programmierstil und Implementierungsdetails abhängt und dadurch Vergleiche zwischen Algorithmen verzerrt werden können.
Beispiel: Zwei Implementierungen desselben Algorithmus (eine „clever“, eine „umständlich“) können unterschiedlich viele Source-Code-Anweisungen haben, obwohl die algorithmische Idee identisch ist.

Man zählt bewusst eine problemtypische Kernoperation (z.B. Schlüsselvergleiche beim Sortieren), weil das die Vergleichbarkeit zwischen Algorithmen für dasselbe Problem verbessert.
Beispiel: Beim Sortieren kann man die Zahl der Vergleiche zwischen Elementen zählen; damit lassen sich Sortierverfahren unabhängig von Hardware/Compiler vergleichen.

Man ignoriert möglicherweise laufzeitrelevante Teile des Ablaufs und erhält eher geringe Aussagekraft über die absolute Laufzeit in Sekunden.
Beispiel: Zwei Sortieralgorithmen können ähnlich viele Vergleiche haben, aber sehr unterschiedliche Kosten durch Speicherzugriffe oder Swap-Operationen verursachen, die dann im Maß nicht vollständig sichtbar sind.

T(N) ist die Worst-Case-Laufzeit für die ungünstigste Eingabe der Größe N.
Tmin(N) ist die Best-Case-Laufzeit für die günstigste Eingabe der Größe N.
Tavg(N) ist die durchschnittliche Laufzeit über alle Eingaben der Größe N (oft relevant, aber analytisch schwer).
Beispiel (lineare Suche): Worst Case: Element nicht vorhanden → ~N Vergleiche; Best Case: Element an Position 0 → 1 Vergleich; Average Case hängt von der Verteilung ab.

Weil er eine obere „Sicherheitsgarantie“ liefert (wie schlecht es maximal werden kann) und in der Regel analytisch gut erfassbar ist.
Beispiel: Bei einem System mit Zeitlimits (z.B. Echtzeit/Service-Level) ist der Worst Case entscheidend, weil er bestimmt, ob Deadlines sicher eingehalten werden.

Weil er nur für besonders günstige Eingaben gilt und damit oft wenig über das typische Verhalten aussagt.
Beispiel: Wenn ein Sortieralgorithmus im Best Case linear ist, aber im Normalfall quadratisch, hilft dir der Best Case kaum bei der Auswahl für reale Daten.

Weil man dafür Annahmen über die Verteilung der Eingaben machen muss, und diese Annahmen sind häufig nicht eindeutig oder mathematisch komplex.
Beispiel: In der Maximumsuche ist die Anzahl der Maximum-Updates vom konkreten Eingabemuster abhängig; Worst/Best sind leicht, Average ist schwieriger.

Bei der Maximumsuche sind viele Teilschritte (Initialisierung, Abbruchbedingung prüfen, Vergleich „neues Maximum?“, Index fortschreiben) in ihrer Häufigkeit unabhängig von der konkreten Eingabe, aber die „Aktualisierung des Maximums“ hängt von der Eingabe ab.
Beispiel: Worst Case: bei streng steigender Folge wird fast jedes Element ein neues Maximum → viele Updates; Best Case: Maximum liegt schon „richtig“, Updates bleiben aus.

Typische Klassen sind z.B. O(1), O(log N), O(N), O(N log N), O(N²), O(N³), O(2^N).
Beispiel: Binäre Suche liegt typischerweise in O(log N), während ein einfacher doppelt geschachtelter Vergleich über Paare oft O(N²) ist.

Konstante Faktoren ändern das asymptotische Wachstum nicht; das Verhältnis (z.B. 2·N zu 3·N) bleibt für jedes N konstant, daher bildet O-Notation diese Details nicht ab.
Beispiel: 2·N und 100·N sind beide linear und unterscheiden sich nur um einen konstanten Faktor, während N und N² sich mit wachsendem N drastisch auseinanderentwickeln.

Konstante Summanden beeinflussen das Wachstum für große N nicht, weil sie gegenüber wachsenden Termen asymptotisch vernachlässigbar sind.
Beispiel: N² + 5 wächst für große N praktisch wie N²; die „+5“ spielt keine Rolle mehr.

Für N → ∞ dominiert bei Summen von Monomen der Term mit dem größten Exponenten das Wachstum, daher bestimmt er die O-Klasse.
Beispiel: 2·N² + N + 5 ist in O(N²), weil N² gegenüber N und Konstanten dominiert.

Es bedeutet: T(N) wächst asymptotisch nicht schneller als f(N), also f(N) ist eine obere Schranke für das Wachstum von T(N).
Beispiel: Wenn ein Algorithmus maximal proportional zu N² Schritte benötigt, dann ist T(N) ∈ O(N²).

Weil O nur eine obere Schranke ist: „langsamer wachsen“ ist erlaubt, daher ist eine weniger enge Schranke immer noch wahr, aber weniger aussagekräftig.
Beispiel: Lineare Suche ist O(N), aber auch O(N²); sinnvoll ist meist die strengstmögliche (engste) obere Schranke, also O(N).

O ist eine obere Wachstumsschranke, Ω eine untere Wachstumsschranke und Θ beschreibt „genaues“ asymptotisches Wachstum (tight bound).
Beispiel: Wenn T(N) sowohl in O(N²) als auch in Ω(N²) liegt, dann ist T(N) in Θ(N²).

Alle drei Notationen (O, Ω, Θ) können jeweils auf T(N), Tmin(N) und Tavg(N) angewendet werden (also obere/untere/exakte Schranken für Worst/Best/Average).
Beispiel: Für Insertion Sort kann man getrennt Aussagen für Worst Case (T), Best Case (Tmin) und Average Case (Tavg) in O/Ω/Θ machen.

Alle drei Notationen (O, Ω, Θ) können jeweils auf T(N), Tmin(N) und Tavg(N) angewendet werden (also obere/untere/exakte Schranken für Worst/Best/Average).[Anhang]

Wenn mehrere Teilaufwände addiert werden, ist am Ende die am stärksten wachsende Komplexität entscheidend (die „dominante“).[Anhang]

Beispiel: O(N) + O(N log N) ergibt insgesamt O(N log N), weil N log N stärker wächst als N.

Eine einzelne einfache Anweisung (z.B. Zuweisung) ist O(1); enthält sie Funktionsaufrufe, werden deren Laufzeiten in O-Notation hinzuaddiert (und die dominante zählt).[Anhang]

Beispiel: `x = foo(y);` ist nicht automatisch O(1), sondern hängt von der Komplexität von `foo` ab (z.B. O(N)).[Anhang]

Man addiert die Laufzeiten der Anweisungen; in O-Notation bleibt die dominante Komplexität übrig.[Anhang]

Beispiel: Erst O(N) für „findMax“, danach O(N log N) für „sort“ ⇒ Gesamt O(N log N).

Man berücksichtigt die Laufzeit des Bedingungsausdrucks (meist O(1), außer bei Funktionsaufrufen) und die Laufzeiten der then/else-Zweige; für Worst-Case nimmt man den teureren Zweig als maßgeblich.

Beispiel: Wenn im then-Zweig O(N log N) passiert und im else-Zweig O(N), dann ist das if insgesamt O(N log N).

Man multipliziert „Anzahl der Iterationen“ mit der Laufzeit des Schleifenrumpfs (inklusive Kosten für die Bedingungsprüfung und Funktionsaufrufe darin).

Beispiel: Wenn die Schleife N-mal läuft und der Rumpf O(1) ist, ist die Schleife O(N).