Nombre de complexité

Discutez d'informatique ici !
nawfel
Membre Naturel
Messages: 16
Enregistré le: 18 Jan 2008, 21:03

Nombre de complexité

par nawfel » 20 Jan 2008, 22:46

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
Membre Relatif
Messages: 134
Enregistré le: 28 Avr 2006, 20:53

par eusebius » 21 Jan 2008, 10:03

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é

 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite