Big-O beschreibt, wie sich die Laufzeit oder der Speicherverbrauch eines Algorithmus vergrößert, wenn die Eingabegröße n wächst. Sie erfasst das Worst-Case-Asymptotik-Verhalten und ignoriert Konstanten und Terme niedrigerer Ordnung.
Wir kümmern uns um die Wachstumsrate, nicht um die genaue Anzahl der Schritte. O(2n + 5) ist einfach O(n), denn wenn n groß wird, spielen Konstanten und kleinere Terme keine Rolle mehr.
| Big-O | Name | Beispiel |
|---|---|---|
| O(1) | konstant | Array-Index-Zugriff |
| O(log n) | logarithmisch | binäre Suche |
| O(n) | linear | Durchsuchen einer Liste |
| O(n log n) | linearithmisch | Merge Sort |
| O(n²) | quadratisch | verschachtelte Schleifen |
| O(2ⁿ) | exponentiell | naive Teilmengen |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
Big-O verbirgt Konstanten: Ein O(n)-Algorithmus mit einer riesigen Konstante kann gegen O(n log n) bei kleinen Eingaben verlieren. Verfolgen Sie auch die Speicher-Komplexität, nicht nur die Zeit.
Big-O ermöglicht es dir, Algorithmen zu vergleichen, ohne sie auszuführen oder dich um Hardware zu sorgen.
Es sagt voraus, welche Lösungen bestehen bleiben, wenn die Eingaben von Hunderten auf Millionen wachsen — der Unterschied zwischen einem Feature, das skaliert, und einem, das zeitlich überschritten wird.
Es ist das Vokabular, das jeder Ingenieur verwendet, um über Leistung nachzudenken.