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 » indique l’ordre de grandeur, ex. O(n) = linéaire
Concepts en informatique

Complexité temporelle – analogie de bureau

Un graphique montrant diverses complexités en notation Big O

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

Complexité spatiale – analogie de bureau

Un graphique montrant diverses complexités en notation Big O

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

Passons à la pratique !

Concepts en informatique

Preparing Video For Download...