⏱️
Vorlesung 5
Komplexität & Big-O —
wie wir Algorithmen vergleichen
Fortgeschrittene Algorithmen und Programmierung
Prof. Dr. Alexandra Mikityuk
HTW Berlin
Eine Sprache, mit der man Algorithmen wirklich vergleichen kann
Lernziele
- Verstehen, warum wir eine formale Sprache für Algorithmen-Geschwindigkeit brauchen
- Die Big-O-Notation lesen und schreiben können
- Die 7 wichtigsten Komplexitätsklassen auswendig kennen — von O(1) bis O(n!)
- Für gegebenen Code die Big-O-Komplexität bestimmen können
- Laufzeit in C mit
clock() messen
- Verstehen, warum ein besserer Algorithmus mehr bringt als schnellere Hardware
Das ist die wichtigste Vorlesung des Semesters für die Klausur. Hier wird das Vokabular gelegt, mit dem wir alle folgenden Algorithmen vergleichen werden.
Themen heute
Teil 1 — Konzept
- Das Problem: wie schnell ist „schnell"?
- Big-O-Notation einführen
- Die 7 Komplexitätsklassen
- Wachstum visuell + konkrete Zahlen
Teil 2 — Anwendung
- Code analysieren — das 3-Schritte-Rezept
- Bubble/Selection/Insertion erneut bewertet
- C-Primitive:
clock() für echtes Messen
- Hardware vs. Algorithmus — was bringt mehr?
Brücke: in Vorlesung 4 hatten wir gesagt „alle drei Sort-Algorithmen wachsen mit n × n". Heute machen wir aus dem n × n ein offizielles Etikett.
Das Problem — wie schnell ist „schnell"?
Stellt euch vor: ihr habt zwei Algorithmen, die dasselbe Problem lösen. Welcher ist besser?
🤔 Naive Antwort
„Lass beide laufen und stoppe die Zeit."
Aber: bei welcher Eingabegröße? Auf welchem Rechner? Mit welchem Compiler? Bei n=10 oder n=10 Millionen?
✓ Bessere Antwort
„Schauen wir uns an, wie die Laufzeit wächst, wenn die Eingabe größer wird."
Das ist hardware-unabhängig, sprach-unabhängig — eine reine Eigenschaft des Algorithmus.
Big-O ist die Notation, mit der wir genau diese Wachstumseigenschaft beschreiben. Eine universelle Sprache.
Erinnerung an Vorlesung 3: Summe 1..N
Wir hatten zwei Lösungen — und einen 3.000.000× Unterschied:
🐢 Lösung A — Schleife
long long summe_schleife(long long n) {
long long s = 0;
for (long long i = 1; i <= n; i++)
s += i;
return s;
}
n Operationen — wächst linear mit n.
🚀 Lösung B — Gauß-Formel
long long summe_gauss(long long n) {
return n * (n + 1) / 2;
}
3 Operationen — bleibt konstant, egal wie groß n wird.
Big-O sagt: Lösung A ist O(n) — Lösung B ist O(1). Das sind unsere ersten zwei Komplexitätsklassen.
Big-O — die Notation
O(f(n))
heißt: „die Laufzeit wächst höchstens so schnell wie f(n) — wenn n groß genug wird."
Lesart 1 — wörtlich
O(n²) = „Order of n-squared"
Sprich: „Big-O von n-Quadrat"
Lesart 2 — informell
Wenn die Eingabe doppelt so groß wird — wie viel länger braucht der Algorithmus?
- O(1): gar nicht länger
- O(n): doppelt so lange
- O(n²): vier mal so lange
Was Big-O sagt — und was nicht
✅ Big-O sagt:
- Wie wächst die Laufzeit mit größerer Eingabe?
- Welcher Algorithmus skaliert besser?
- Wie viele Operationen ungefähr?
❌ Big-O sagt nicht:
- Wie viele Sekunden eine konkrete Ausführung dauert
- Wie schnell euer Prozessor ist
- Welcher Algorithmus bei kleinen n schneller ist
Wichtige Faustregel: Konstanten werden ignoriert. O(100·n) wird zu O(n), O(n² + 5n + 3) wird zu O(n²). Interessant ist nur der schnellste wachsende Term.
Die wichtigsten 7 Komplexitätsklassen
| Big-O | Name | Beispiel-Algorithmus | Bewertung |
|---|
| O(1) | konstant | Array-Zugriff arr[i] | ✨ perfekt |
| O(log n) | logarithmisch | Binäre Suche | 🚀 sehr gut |
| O(n) | linear | Array durchsuchen (lineare Suche) | 👍 gut |
| O(n log n) | loglinear | Merge Sort, Quick Sort | 🆗 akzeptabel |
| O(n²) | quadratisch | Bubble/Selection/Insertion Sort | ⚠️ problematisch |
| O(2ⁿ) | exponentiell | Brute-Force Passwort | 💀 katastrophal |
| O(n!) | faktoriell | Alle Permutationen einer Liste | ☠️ unmöglich |
Diese Tabelle solltet ihr auswendig können. Sie kommt in der Klausur, in jedem Algorithmen-Buch und in jedem technischen Interview.
Wachstumsvergleich bei n = 1.000
O(log n)
~ 10 Operationen
O(n log n)
~ 10.000 Operationen
O(n²)
1.000.000 Operationen
O(2n)
~ 10301 — länger als das Alter des Universums
💡 Exponentielle Algorithmen sind unbenutzbar selbst bei kleinen Eingaben. Bei n = 100: schon mehr Operationen als Atome im Universum.
Konkrete Zeit — wie lange dauert das wirklich?
Annahme: moderner Rechner schafft ~ 10⁹ Operationen pro Sekunde.
| Komplexität | n = 10 | n = 1.000 | n = 1.000.000 |
|---|
| O(1) | <1 µs | <1 µs | <1 µs |
| O(log n) | <1 µs | <1 µs | <1 µs |
| O(n) | <1 µs | 1 µs | 1 ms |
| O(n log n) | <1 µs | 10 µs | 20 ms |
| O(n²) | <1 µs | 1 ms | 16 Minuten |
| O(2ⁿ) | 1 µs | ∞ Universum | ∞ |
Merke: ein O(n²)-Algorithmus, der bei 1.000 Elementen noch in 1 ms läuft, braucht bei einer Million Elementen schon 16 Minuten.
Wie analysiere ich Code? — Das 3-Schritte-Rezept
① Schleifen zählen
Wie viele Iterationen hat die innerste Schleife? n-mal? n/2-mal? log n-mal?
② Verschachtelung prüfen
Liegt eine Schleife in einer anderen? Dann multiplizieren. Sind sie sequenziell? Dann addieren.
③ Konstanten weglassen
O(3n + 5) → O(n)
O(n² + 10n) → O(n²)
Faustregel für die Klausur: nach dem 3. Schritt bleibt nur der schnellste wachsende Term übrig, und ohne Konstanten.
Beispiel 1 — eine einfache Schleife
int summe = 0;
for (int i = 0; i < n; i++) {
summe += i;
}
Analyse:
- Schritt ①: die Schleife läuft n-mal
- Schritt ②: keine Verschachtelung
- Schritt ③: keine Konstanten
→ O(n)
Beispiel 2 — verschachtelte Schleifen
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d,%d\n", i, j);
}
}
Analyse:
- Schritt ①: innere Schleife läuft n-mal
- Schritt ②: liegt in äußerer Schleife →
n × n = n²
- Schritt ③: keine Konstanten
→ O(n²)
Beispiel 3 — Verschachtelt vs. nacheinander
Verschachtelt — O(n²)
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
work();
}
}
n × n = n² Aufrufe
Sequenziell — O(n)
for (i = 0; i < n; i++) {
work();
}
for (j = 0; j < n; j++) {
work();
}
n + n = 2n → n Aufrufe
Goldene Regel: Verschachtelte Schleifen über dasselbe n → multiplizieren. Nacheinander → addieren (und Konstanten weg).
Beispiel 4 — wenn jeder Schritt halbiert
while (n > 1) {
n = n / 2;
work();
}
Bei n = 1.024: wie oft kann man halbieren, bis 1 übrig bleibt?
1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1
Das sind 10 Schritte bei n = 1.024 = 2¹⁰. Allgemein: log₂(n) Schritte.
→ O(log n)
Wo trifft man das in der Praxis? Binäre Suche, balancierte Bäume, Divide-and-Conquer. Sehr gute Komplexitätsklasse.
Best Case · Average Case · Worst Case
Beispiel: lineare Suche in einem Array mit n Elementen.
🌟 Best Case
Element ist gleich das erste → 1 Vergleich
O(1)
📊 Average Case
Im Durchschnitt halbes Array → n/2 Vergleiche
O(n)
💀 Worst Case
Element ist letzte / fehlt → n Vergleiche
O(n)
Konvention: wir geben standardmäßig den Worst Case an. Das ist die Garantie, die wir unseren Nutzern geben — schlimmer wird es nicht.
Anwendung — unsere drei Sort-Algorithmen aus Vorlesung 4
Jetzt geben wir ihnen ihr offizielles Big-O-Etikett:
| Algorithmus | Best Case | Worst Case | Bewertung |
|---|
| Bubble Sort | O(n) | O(n²) | einfach, aber langsam |
| Selection Sort | O(n²) | O(n²) | immer langsam, aber wenige Tausche |
| Insertion Sort | O(n) | O(n²) | top für fast-sortierte Daten |
Wichtig: alle drei sind im Worst Case O(n²) — bei großen Daten unbrauchbar. Nächste Woche (Vorlesung 6) lernen wir O(n log n)-Algorithmen kennen: Merge Sort und Quick Sort.
C-Primitive: Zeit messen mit clock()
Big-O ist die Theorie. Aber wie messen wir die echte Laufzeit eines C-Programms? Mit clock() aus <time.h>.
#include <stdio.h>
#include <time.h>
int main() {
clock_t start = clock();
summe_schleife(1000000000LL);
clock_t ende = clock();
double sek = (double)(ende - start) / CLOCKS_PER_SEC;
printf("Dauer: %.6f Sekunden\n", sek);
return 0;
}
CLOCKS_PER_SEC ist eine Konstante aus <time.h> — typisch 1.000.000 auf Linux/macOS. Sie sagt, wie viele „Ticks" eine Sekunde sind.
Warum der (double)-Cast?
Schaut euch diese Zeile genau an:
double sek = (double)(ende - start) / CLOCKS_PER_SEC;
❌ Ohne Cast
sek = (ende - start) / CLOCKS_PER_SEC;
Beide Seiten sind int-artig → C macht Ganzzahl-Division. Bei 50.000 / 1.000.000 → 0. Alle Nachkommastellen weg!
✓ Mit Cast
sek = (double)(ende-start) / CLOCKS_PER_SEC;
Der Cast macht die linke Seite zu double → C macht Fließkomma-Division. Ergebnis: 0,05 Sekunden.
Klausur-Klassiker: wer den Cast vergisst, bekommt immer 0.000000 Sekunden raus — egal wie langsam der Algorithmus war.
Moore's Law vs. besserer Algorithmus
Mooresches Gesetz (1965): die Rechenleistung verdoppelt sich etwa alle 2 Jahre.
Klingt großartig. Aber was bedeutet das wirklich für unsere Algorithmen?
💻 Doppelt schnellerer Rechner
Bei einem O(n²)-Algorithmus könnt ihr nur √2 ≈ 1,41× mehr Daten in derselben Zeit verarbeiten.
Also nur 41% mehr Eingabe — nicht 100%.
🧠 Besserer Algorithmus (O(n²) → O(n log n))
Bei n = 1 Mio. Elementen: ~ 50.000× weniger Operationen.
Ein besserer Algorithmus schlägt 30 Jahre Hardware-Fortschritt.
Konsequenz: Hardware kaufen ist teuer und nur linear besser. Algorithmen-Wissen ist umsonst und exponentiell besser. Deshalb diese Vorlesung.
Rechenleistung kostet Energie — Geld — CO₂
Jede Rechenoperation kostet Strom. Bei Milliarden Nutzern wird das real:
💰 Geld
Google-Server weltweit: ca. 260 Mio. € Stromkosten pro Jahr. Halbierung der Operationen = halber Stromrechnung.
🌍 CO₂
ICT-Branche verursacht ca. 3-4% der weltweiten CO₂-Emissionen — mehr als die gesamte Luftfahrt.
🔋 Akku
Schlechter Algorithmus in einer App = Handy-Akku leer nach 2 h statt 12 h. Bessere Algorithmen = längere Akku-Laufzeit.
Green Coding: ein effizienter Algorithmus spart nicht nur Zeit, sondern auch Energie, Geld und CO₂. Komplexität ist auch eine Umwelt-Frage.
Was passiert auf der CPU?
Wenn wir „eine Operation" sagen, was tut die CPU eigentlich? Eine scheinbar einfache Zeile in C:
summe += arr[i];
Speicher-Hierarchie der CPU (von schnell zu langsam):
- 🟢 CPU-Register: < 1 ns (Nanosekunde) — aktive Werte (z.B.
i in der Schleife)
- 🟡 L1/L2-Cache: 1–10 ns — kürzlich benutzte Daten
- 🟠 RAM: ~ 100 ns — alles, was nicht mehr im Cache passt
Ein schlechter Algorithmus zwingt die CPU, ständig aus RAM statt aus dem Cache zu lesen — das ist ~100× langsamer. Genau das macht O(n²) bei großen Arrays so spürbar weh.
🧠 Quiz 1
Ein Algorithmus hat die Komplexität O(n²) und braucht bei 1.000 Elementen 1 Sekunde. Wie lange dauert er bei 10.000 Elementen?
A) ca. 1 Sekunde
B) ca. 10 Sekunden
C) ca. 100 Sekunden
D) ca. 1.000 Sekunden
Tipp: 10× mehr Eingabe bei O(n²) → wie viel mehr Zeit?
🧠 Quiz 2
Welche Big-O-Notation hat dieser Code?
for (i = 0; i < n; i++)
printf("%d", i);
for (j = 0; j < 100; j++)
printf("x");
A) O(1)
B) O(n)
C) O(n²)
D) O(100n)
Tipp: O(n + 100) = ? — Konstanten werden weggelassen, die zweite Schleife hängt nicht von n ab.
Zusammenfassung
- Big-O beschreibt, wie die Laufzeit mit wachsender Eingabe skaliert — sprach- und hardware-unabhängig.
- Wichtige Klassen auswendig: O(1) · O(log n) · O(n) · O(n log n) · O(n²) · O(2ⁿ) · O(n!).
- Analyse-Rezept: Schleifen zählen · Verschachtelung prüfen · Konstanten weglassen.
- Verschachtelt = multiplizieren · sequenziell = addieren.
- Best/Worst/Average Case unterscheiden — standardmäßig Worst Case angeben.
- In C:
clock() für echte Messung — aber den (double)-Cast nicht vergessen!
- Besserer Algorithmus schlägt schnellere Hardware. Algorithmen sind grüner.
Wichtig für die Klausur
- ✅ Die 7 Komplexitätsklassen auswendig (O(1) bis O(n!))
- ✅ Für ein Code-Snippet die Big-O bestimmen können
- ✅ Unterschied verschachtelt vs. sequenziell verstehen
- ✅ Warum Konstanten ignoriert werden
- ✅ Zusammenhang Algorithmus ↔ Rechenleistung ↔ Energie
- ✅ Code mit
clock() messen + Cast erklären können
📚 Nächste Woche — Vorlesung 6: wir bauen Merge Sort und Quick Sort — die ersten O(n log n)-Sortier-Algorithmen. Mit Divide-and-Conquer.