Nombre de complexité

[nawfel]

Bonjour,
En fait j'ai deux quest°:c'est quoi
-un algorithme de compléxité polynomiale
- le nombre de complexité dans un problème d'optimisation(O(n!))
Merci d'avance.

[eusebius]

La complexité d'un algorithme, c'est une mesure du temps qu'il faut pour l'exécuter (complexité en temps), ou de l'espace mémoire qu'il va utiliser (complexité en espace). Par défaut lorsque rien n'est précisé, on parle de complexité en temps.

On peut mesurer la complexité algorithmique dans le pire cas, dans le meilleur cas, ou encore faire une estimation de l'espérance en complexité (en moyenne). Par défaut, lorsque rien n'est précisé, on travaille toujours dans le pire cas.

La complexité est exprimée en fonction d'un paramètre, qui est normalement la taille d'un paramètre d'entrée. Pour la complexité en temps, on va par exemple mesurer le nombre d'opérations élémentaires qu'il faut faire pour exécuter l'algorithme sur une entrée de taille n.

Un algorithme de complexité polynomiale est un algorithme dont la complexité (son ordre de grandeur en fait) s'exprime comme un polynôme de la taille n du paramètre d'entrée.
Par exemple, un problème en O(n^3) est de complexité polynomiale (classe PTIME), un problème en O(3^n) est de complexité exponentielle (classe EXPTIME), un problème en O(4 log n) est de complexité logarithmique (classe L).

Je suppose que si l'on te parle de complexité algorithmique c'est que tu connais la notation O().

Quant à la notion de "nombre de complexité" c'est la première fois que j'en entends parler...

Article Wikipédia sur la complexité