/ Informatik

Algorithmen & Komplexität

Asymptotische Laufzeiten (O(1), O(log n), O(n), O(n log n), O(n²)), Master-Theorem, binäre Suche, Vergleichsanzahl klassischer Sortierverfahren und Rekursionstiefe.

14 Rechner in dieser Kategorie, jeweils mit automatischer Variablen-Umstellung.

I01

O-Notation Vergleich

Vergleicht die Operationsanzahl verschiedener Komplexitätsklassen für eine Eingabegröße n. Hier konkret: Wert von O(log n) = log₂(n).

I02

Laufzeit linear O(n)

Operationsanzahl bei linearer Komplexität: Ops = n · k. Jedes Element wird mit konstantem Aufwand k bearbeitet.

I03

Laufzeit quadratisch O(n²)

Operationsanzahl bei quadratischer Komplexität: Ops = n². Typisch für verschachtelte Schleifen über dieselbe Eingabe.

I04

Master-Theorem (Fall 1)

Rekurrenz T(n) = a·T(n/b) + O(n^c). Im Fall 1 (c < log_b(a)) dominiert die Rekursion: T(n) = O(n^(log_b(a))).

I05

Master-Theorem (Fall 2)

Rekurrenz T(n) = a·T(n/b) + O(n^c). Im Fall 2 (c = log_b(a)) tragen Rekursion und Kombinieren gleich bei: T(n) = O(n^c · log n).

I06

Master-Theorem (Fall 3)

Rekurrenz T(n) = a·T(n/b) + O(n^c). Im Fall 3 (c > log_b(a)) dominiert der Kombinieren-Schritt: T(n) = O(n^c).

I07

Binäre Suche Schritte

Maximale Anzahl Schritte (Vergleiche) der binären Suche in einem sortierten Array: Schritte = ⌈log₂(n)⌉.

I08

Bubble Sort Vergleiche

Anzahl Vergleiche im Worst Case beim Bubble Sort: Vergleiche = n · (n − 1) / 2. Wächst quadratisch mit n.

I09

Selection Sort Vergleiche

Anzahl Vergleiche beim Selection Sort — unabhängig von der Eingabereihenfolge: Vergleiche = n · (n − 1) / 2.

I10

Merge Sort Vergleiche

Anzahl Vergleiche beim Merge Sort (Divide & Conquer): Vergleiche = n · log₂(n). Garantierte O(n log n)-Laufzeit.

I11

Quick Sort Vergleiche (Average)

Durchschnittliche Anzahl Vergleiche beim Quick Sort: Vergleiche ≈ 1,39 · n · log₂(n). Im Worst Case (schlechter Pivot) entartet er zu O(n²).

I12

Heap Sort Vergleiche

Anzahl Vergleiche beim Heap Sort im Worst Case: Vergleiche = 2 · n · log₂(n). Garantierte O(n log n)-Laufzeit ohne zusätzlichen Speicher.

I13

Rekursionstiefe Binärraum

Maximale Rekursionstiefe bei halbierender Teilung des Problems: Tiefe = ⌊log₂(n)⌋. Begrenzt den benötigten Stack.

I14

Laufzeit O(n · log n)

Operationsanzahl bei O(n log n)-Komplexität: Ops = n · log₂(n). Typisch für effiziente Sortierverfahren und Divide-&-Conquer-Algorithmen.