Complexité algorithmique : Différence entre versions

De WikiMéca
Sauter à la navigation Sauter à la recherche
(Page créée avec « ==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. ===Comp... »)
 
(Notion de complexité)
Ligne 6 : Ligne 6 :
 
===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.
Par exemple, si le programme nécessite le stockage de données dans un tableau N×N, la complexité en mémoire est de O().
+
Par exemple, si le programme nécessite le stockage de données dans un tableau N×N, la complexité en mémoire est de <math>\Omicron(N^2)</math>.
 +
===Notation "Omicron"===
 +
La notation "grand O" ou "Omicron" de Landau dénote le caractère dominé d'une fonction par rapport à une autre.
 +
 
 +
Soient <math>''f''</math> et <math>''g''</math> deux fonctions de la variable réelle <math>''x''</math>. On dit que <math>''f''</math> est dominée par <math>''g''}} en <math>+∞</math>, ou que <math>''g''</math> domine <math>''f''</math> en <math>+∞</math>, et on note :
 +
<math>f(x)=O(g(x)) \ (x\rightarrow\infty),</math>
 +
 
 +
lorsqu'il existe des constantes <math>''N''}} et <math>''C''</math> telles que
 +
<math>\forall x>N\qquad \left|f(x)\right| \le C \left|g(x)\right|.</math>
 +
 
 +
Intuitivement, cela signifie que <math>''f''</math> ne croît pas plus vite que <math>''g''</math>.

Version du 19 août 2019 à 18:23

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 Échec d'analyse (erreur de syntaxe): {\displaystyle ''g''}} en <math>+∞} , ou que domine en Échec d'analyse (erreur de syntaxe): {\displaystyle +∞} , et on note :

lorsqu'il existe des constantes Échec d'analyse (erreur de syntaxe): {\displaystyle ''N''}} et <math>''C''} telles que

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