Complexité

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

Ce contenu est réservé aux membres uniquement. Veuillez vous %connecter%.

Vous aimerez aussi...

Laisser un commentaire

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

*

code