Révision

Ce qu’il faut savoir

• Un algorithme est la spécification d'un schéma de calcul sous forme d'une suite finie d'opérations élémentaires obéissant à un enchaînement déterminé.

• Quand on écrit un algorithme, on utilise un langage dit "langage naturel" ("tant que", "si"...), ce langage naturel permet de passer facilement à un langage de programmation (Python, Java...), on dit alors que l'on implémente l'algorithme.

• La notion de complexité d'un algorithme va rendre compte de l'efficacité de cet algorithme. Il existe 2 types de complexité : une complexité en temps et une complexité en mémoire. Nous nous intéresserons ici uniquement à la complexité en temps. La complexité en temps est directement liée au nombre d'opérations élémentaires qui doivent être exécutées afin de résoudre un problème donné.

• Nous nous intéresserons uniquement à la complexité en temps “dans le pire cas”

• Pour comparer des algorithmes, nous allons uniquement nous intéresser à ce que l'on appelle "l'ordre de grandeur asymptotique" (notation O)

Ce qu’il faut savoir faire

• vous devez être capable d’analyser le fonctionnement d’un algorithme (faire tourner un algorithme “à la main”)

• vous devez être capable de déterminer la complexité en temps dans le pire des cas d’un algorithme (exemples : O(n), O(n²), O(log₂(n))...)