Complexité algorithmique

De WikiMéca
Révision datée du 19 août 2019 à 18:25 par Gdumont (discussion | contributions) (Notation "Omicron")
Sauter à la navigation Sauter à la recherche

Notion de complexité

Etudier la complexité d'un algorithme permet de l'optimiser afin qu'il utilise le moins de temps et le moins d'espace mémoire possible.

Complexité en temps

La complexité algorithmique en temps représente la "rapidité" d'un algorithmique à résoudre un problème. C'est une notion relative car elle permet de comparer les rapidités de deux algorithmique résolvant le même problème mais pas de donner un temps de exécution précis, celui-ci dépendant de la machine sur lequel le programme est exécuté.

Complexité en mémoire

Lors de l’exécution du programme, des données sont stockées. La complexité en mémoire mesure l’espace occupé pendant l’exécution. Par exemple, si le programme nécessite le stockage de données dans un tableau N×N, la complexité en mémoire est de .

Notation "Omicron"

La notation "grand O" ou "Omicron" de Landau dénote le caractère dominé d'une fonction par rapport à une autre.

Soient et deux fonctions de la variable réelle . On dit que est dominée par en , ou que domine en , et on note :

lorsqu'il existe des constantes et telles que

Intuitivement, cela signifie que ne croît pas plus vite que .