Complexité temporelle
Comment le temps d'exécution évolue avec la taille d'entrée (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["Complexité temporelle"]:::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;
🧒 Explique-moi comme si j'avais 5 ans
Imagine que tu comptes combien d'étapes il faut pour trouver un jouet. Si tu le trouves toujours immédiatement, c'est O(1). Si tu vérifies chaque boîte une par une, c'est O(n). La complexité temporelle nous dit combien plus longtemps les choses prennent quand on a plus de trucs !
🤓 Expert Deep Dive
L'analyse amortie moyenne les coûts sur des séquences. Big-Θ (borne serrée), Big-Ω (borne inférieure) complètent Big-O. Le théorème maître résout les récurrences T(n) = aT(n/b) + f(n). Les performances pratiques peuvent différer de Big-O en raison des facteurs constants et des effets de cache.