Begriff

Big O Notation

Computer Science Algorithms S3

2 Quellen 0 Lernpfade 0 Backlinks enriched

Warum wichtig?

Dieser Begriff ist ein Knoten im SengakujiWorks-Wissensnetz. Nutze Level 0 für die erste Einordnung, Level 1 für Praxis, Level 2 für technische Struktur und Level 3 für Grenzen, Fallstricke und Expertenkontext.

Wie misst man, wie "schnell" ein Algorithmus ist? In Sekunden? Nein, denn auf einem Supercomputer ist alles schnell. Man misst in Schritten abhängig von der Datenmenge (n). Big O beschreibt das Worst-Case-Szenario: "Wie schlimm wird es, wenn die Datenmenge explodiert?"

O(1): Super. Egal ob 1 oder 1000 User, es dauert immer 1 Sekunde.
O(n): Okay. Doppelt so viele User = doppelt so lange warten.
O(n²): Katastrophe. Doppelt so viele User = vierfache Wartezeit.

Merksatz: Eine mathematische Notation, die beschreibt, wie Speicherbedarf oder Laufzeit eines Algorithmus wachsen, wenn die Eingabemenge größer wird.

In jedem Coding-Interview. "Schreib eine Funktion, die Duplikate in einer Liste findet." Wenn du zwei verschachtelte Schleifen schreibst (for x in list: for y in list...), sagt der Interviewer: "Das ist O(n²). Zu langsam! Mach es in O(n)." Dann musst du eine Hash-Map nutzen.

1. Asymptotische Grenzen: Big Theta ($\Theta$) und Big Omega ($\Omega$)

Die Informatik unterscheidet oft nicht sauber genug. Big O, oft als "Laufzeit" betitelt, markiert eigentlich nur die asmyptotische obere Schranke (Worst-Case). Will man den besten Fall (Best-Case) beweisen, spricht man von der $\Omega$-Notation (Big Omega). Z.B. ist das Einfügen in Arrays $\Omega(1)$ wenn man Glück hat. Die $\Theta$-Notation (Big Theta) ist eine "enge Schranke" (Tight Bound). Wenn ein Algorithmus im Best- und im Worst-Case verlässlich $N^2$ Schritte erfordert, redet man von $\Theta(N^2)$. Es bedeutet, die Komplexitätskurve ist präzise gefangen, weder unendlich besser, noch wild schlechter.

2. Master-Theorem für rekursive Funktionen

Wenn jemand eine for-Schleife sieht, ruft er schnell "Oh, das ist O(N)". Was aber, wenn dein Code eine "Divide and Conquer"-Rekursion ist? (z. B. T(n) = 2T(n/2) + O(n)). Um hier die Big-O-Klasse herzuleiten, gibt es in der theoretischen Informatik das Master-Theorem. Es stellt eine Formel bereit, um jede rekursive Differenzengleichung auf einen Schlag zu lösen, indem man Verhältnisse prüft: Ist der Split der Subprobleme (das "Divide") am schwersten liegend oder der Zusammenbau (das "Conquer")? Ohne das Master-Theorem wäre es extrem anmaßend, für Matrix-Multiplikationen wie den Strassen-Algorithmus die komplexe Grenze $O(n^{\log_2{7}}) \approx O(n^{2.81})$ rein gedanklich zu verifizieren.

3. Amortisierte Laufzeit

Big O kann extrem unfair zu Datenstrukturen sein. Nimm ein dynamisches Array (std::vector in C++ oder abstrakte List in Python). Wenn das Array voll ist, muss beim .append() ein doppelt so großes neues Array allokiert und alles dorthin hinkopiert werden. Dieser Worst-Case ist streng genommen $O(n)$. Aber da wir für sehr lange Zeitenden kostenlos anhängen konnten (mit $O(1)$) und den schweren Kopier-Case mathematisch auf alle billigen Aufrufe mitteln, redet man von der Amortisierte Laufzeit O(1). Das ist für Production-Engineers ein essenzielles Konzept, um keine Panik vor eigentlich selten auftauchenden Worst-Cases zu haben.

Quick-Check

Ist O(1) immer schneller als O(n)?
Theoretisch ja. Praktisch nein. O(1) kann bedeuten "Dauert immer 1 Stunde". O(n) kann bei kleinen n (n=5) nur 5 Millisekunden dauern. Big O sagt nur etwas über das Wachstum bei riesigen Datenmengen.
Warum ignorieren wir Konstanten?
Wir schreiben O(n), nicht O(2n + 5). Die Konstanten sind Hardware-Details. Uns interessiert die Kurve (linear vs. quadratisch).
Was ist O(n!)?
Fakultät. Das "Traveling Salesman Problem" (brute force). Der absolute Horror. Schon bei n=20 unlösbar.