Zeitkomplexität
Wie die Laufzeit mit der Eingabegröße skaliert (Big O).
Time complexity measures how the execution time of an algorithm scales as input size (n) increases. It's expressed using Big O notation, which describes the upper bound (worst-case) growth rate.
Common time complexities:
- O(1) Constant: Same time regardless of input (array index access)
- O(log n) Logarithmic: Halves problem each step (binary search)
- O(n) Linear: Time proportional to input (single loop)
- O(n log n) Linearithmic: Efficient sorting (mergesort, quicksort)
- O(n²) Quadratic: Nested loops (bubble sort)
- O(2ⁿ) Exponential: Doubles each step (naive recursion)
Big O focuses on dominant terms as n→∞, ignoring constants and lower-order terms.
graph LR
Center["Zeitkomplexität"]:::main
Pre_algorithm["algorithm"]:::pre --> Center
click Pre_algorithm "/terms/algorithm"
Rel_space_complexity["space-complexity"]:::related -.-> Center
click Rel_space_complexity "/terms/space-complexity"
Rel_algorithm["algorithm"]:::related -.-> Center
click Rel_algorithm "/terms/algorithm"
Rel_big_o_notation["big-o-notation"]:::related -.-> Center
click Rel_big_o_notation "/terms/big-o-notation"
classDef main fill:#7c3aed,stroke:#8b5cf6,stroke-width:2px,color:white,font-weight:bold,rx:5,ry:5;
classDef pre fill:#0f172a,stroke:#3b82f6,color:#94a3b8,rx:5,ry:5;
classDef child fill:#0f172a,stroke:#10b981,color:#94a3b8,rx:5,ry:5;
classDef related fill:#0f172a,stroke:#8b5cf6,stroke-dasharray: 5 5,color:#94a3b8,rx:5,ry:5;
linkStyle default stroke:#4b5563,stroke-width:2px;
🧒 Erkläre es wie einem 5-Jährigen
Stell dir vor, du zählst, wie viele Schritte es braucht, um ein Spielzeug zu finden. Wenn du es immer sofort findest, ist das O(1). Wenn du jede Kiste einzeln prüfst, ist das O(n). Die Zeitkomplexität sagt uns, wie viel länger Dinge dauern, wenn wir mehr haben!
🤓 Expert Deep Dive
Amortisierte Analyse mittelt Kosten über Sequenzen. Big-Θ (enge Grenze), Big-Ω (untere Grenze) ergänzen Big-O. Das Master-Theorem löst Rekurrenzen T(n) = aT(n/b) + f(n). Die praktische Leistung kann aufgrund konstanter Faktoren und Cache-Effekte von Big-O abweichen.