Complexité

[latexpage]

Définition

La complexité, ou le temps d’exécution, d’un programme $P$ (fonction ou procédure) est le nombre d’opérations élémentaires (addition, multiplication, affectation, test, etc…) nécessaires à l’exécution de $P$. Lorsque cette complexité dépend de plusieurs paramètres $n$ et $m$, on dira que $P$ a une complexité en $O(\Phi(n,m))$, lorsqu’il existe trois constantes $A, n_0$ et $m_0$ telles que la complexité de $P$ soit inférieure ou égale à $A\times \Phi(n,m)$, pour tout $n > n_0$ et $m > m_0$.

source : https://gargantua.polytechnique.fr/siatel-web/linkto/mICYYYTEsXY6

Exemple

source : http://igm.univ-mlv.fr/~alabarre/teaching/struct/01-complexite-handout.pdf

Exercice

Algorithmes de tri et complexité : TD6 _ Algorithmes de tri & Complexité

Vous aimerez aussi...

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*

code