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

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