Efficacité des algorithmes : temps d'exécution et complexité spatiale

Concepts en informatique

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Introduction à la notation Big‑O

  • Mesure la croissance du temps et de l'espace selon la taille d'entrée
  • Exemples : $O(n)$, $O(n^2)$, $O(log\, n)$
  • « O » désigne l'ordre de croissance, p. ex. O(n) = linéaire
Concepts en informatique

Complexité temporelle – analogie de bureau

Un graphique présentant diverses complexités en notation Big O

  • $O(1)$ : temps constant – « Coup d'œil » – « constant »
  • $O(log\,n)$ : hausse lente – « Division en piles » – « logarithmique »
  • $O(n)$ : hausse linéaire – « Lecture d'un document » – « linéaire »
  • $O(n\,log\,n)$ : hausse plus rapide – « Tri de piles » – « linéarithmique »
  • $O(n^2)$ : hausse quadratique – « Comparaison de documents » – « quadratique »
Concepts en informatique

Complexité spatiale – analogie de bureau

Un graphique présentant diverses complexités en notation Big O

  • $O(1)$ : espace constant – « Espace de bureau » – « constant »
  • $O(log\,n)$ : hausse lente de l'espace – « Notes minimales » – « logarithmique »
  • $O(n)$ : hausse linéaire – « Papiers autocollants » – « linéaire »
  • $O(n\,log\,n)$ : hausse plus rapide – « Piles temporaires » – « linéarithmique »
  • $O(n^2)$ : hausse quadratique – « Grille de comparaison » – « quadratique »
Concepts en informatique

Passons à la pratique !

Concepts en informatique

Preparing Video For Download...