Pratique d'algorithmes en contexte réel

Concepts en informatique

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Algorithmes courants : tri et recherche

Tri

À utiliser quand il faut ordonner des éléments

Problèmes concrets :

  1. Magasinage en ligne : trier par prix, cote, popularité.
  2. Agenda : trier les événements par date et heure.

Recherche

À utiliser quand il faut retrouver des éléments

Problèmes concrets :

  1. Magasinage en ligne : rechercher un titre de livre.
  2. Soutien à la clientèle : rechercher d'anciens billets par nom de client.
Concepts en informatique

Algorithmes de tri : tri à bulles vs tri rapide

Tri à bulles Une animation qui montre le fonctionnement du tri à bulles

  • Tri à bulles : comparer, échanger, répéter, passage.
  • Complexité : $O(n^2)$.
  • Magasinage en ligne avec des millions d'articles : croît très vite avec le catalogue.

Tri rapide Une animation qui montre le fonctionnement du tri rapide

  • Tri rapide : diviser, pivot, trier, fusionner.
  • Complexité : O(n log n).
  • Magasinage en ligne avec des millions d'articles : plus viable à mesure que le catalogue grandit.
Concepts en informatique

Algorithmes de recherche : linéaire vs binaire

Recherche linéaire Une animation qui montre le fonctionnement de la recherche linéaire

  • Complexité : $O(n)$.
  • Simple : vérifie chaque élément un à un.
  • Recherche linéaire : balayer, comparer, trouver, arrêter.

Recherche binaire Une animation qui montre le fonctionnement de la recherche binaire

  • Complexité : $O(log\,n)$.
  • Efficace, mais exige une liste triée.
  • Recherche binaire : diviser, comparer, éliminer, répéter.
Concepts en informatique

Conclusion

  • Tri à bulles, tri rapide, recherche binaire, recherche linéaire
  • Le tri rapide et la recherche binaire sont plus efficaces sur de grands ensembles de données.
  • Vous devriez maintenant saisir pourquoi l'efficacité d'un algorithme peut transformer une expérience technologique.
Concepts en informatique

Passons à la pratique !

Concepts en informatique

Preparing Video For Download...