Complexité algorithmique : Différence entre versions

De WikiMéca
Sauter à la navigation Sauter à la recherche
(Notation "Omicron")
(Complexité en temps)
Ligne 4 : Ligne 4 :
 
La complexité algorithmique en temps représente la "rapidité" d'un algorithmique à résoudre un problème.
 
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é.
 
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é.
 +
 +
Dans un but de simplification nous considérerons toute opération arithmétique comme étant de coût constant.
 +
 
===Complexité en mémoire===
 
===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.
 
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.

Version du 20 août 2019 à 06:35

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é.

Dans un but de simplification nous considérerons toute opération arithmétique comme étant de coût constant.

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 .