Complexe dimension O(n²)

par **canard76** » 12 Juin 2009, 13:59

Bonjour à tous,

J'ai une petite question (qui va vous paraitre stupide mais bon jme lance quand meme :p).

Je suis en train de faire des statistiques et il apparait à plusieurs reprise O(n²) (ou n^3 ca dépend).
L'auteur parle de complexe etc. ; mais qu'est-ce que ca veut dire ?
Par exemple ici : http://www.eleves.ens.fr/home/benhenda/algos.html
est-ce une question de dimension ?
Je connais les ensembles (R,N,Q etc.) mais O(n²) jamais vu !

Merci beaucoup pour votre aide !

A+,

Canard

par **Monsieur23** » 12 Juin 2009, 14:03

Aloha ;

Il ne parle pas de 'complexe' mais de 'complexité' d'un algorithme.

Si la complexité est en O(n²), cela veut dire qu'il existe une constante a telle que la complexité vaille a*n² pour des grandes valeurs de n.

par **SimonB** » 13 Juin 2009, 07:31

Monsieur23 a écrit:Si la complexité est en O(n²), cela veut dire qu'il existe une constante a telle que la complexité vaille a*n² pour des grandes valeurs de n.

Plutôt imprécis, on croirait entendre un analyste :ptdr:

Plus justement : si la complexité est en O(n²), cela veut dire qu'il existe une constante a telle que la complexité est plus petite que a*n² à partir d'un certain rang.

par **Monsieur23** » 13 Juin 2009, 09:25

SimonB a écrit:Plutôt imprécis, on croirait entendre un analyste :ptdr:

On fait de l'informatique ou on fait pas de l'informatique ? :ptdr:

Complexe dimension O(n²)

Complexe dimension O(n²)

Qui est en ligne