complexité algorithmique

Salut,

J'aimerais savoir comment calculer la complexité algorithmique d'un algorithme quelconque? Comment procéder?Je sais qu'il y a complexité logarithmique, polynomiale,...Quelle différence qui existe entre elles?
Autre question, y a t-il une relation entre analyse pire de cas et meilleur cas?
Par avance, merci!

Je vous présente une explication simplifiée en ce qui concerne la complexité algorithmique: http://www.sendspace.com/file/4nsihj

Lamice a écrit:Je vous présente une explication simplifiée en ce qui concerne la complexité algorithmique: http://www.sendspace.com/file/4nsihj

Merci pour le document. Je vais le lire.
Si je ne comprends pas quelque chose je reviendrai au forum pour demander votre aide.
A+

Pour ce sujet,
je vous présente ces deux documens:

Introduction à la complexité - calculs simples


Règles de calculs avec la notation O

Et n'hésitez pas à poser vos questions!!

@algohost: Peux-tu m'expliquer comment il a été prouvé que le meilleur algorithme de tri est de complexité O(nLogn) ?

methodiX a écrit:@algohost: Peux-tu m'expliquer comment il a été prouvé que le meilleur algorithme de tri est de complexité O(nLogn) ?

Oui, je ferai la démonstration avec l'arbre de choix,
en fait on crée un arbre binaire avec les possibilité de comparaison, un tel arbre va avoir comme nombre de feuilles n! (factoriel) valeurs différentes correspodantes aux différentes dispositions (permutations possible) en supposant au départ une table quelconque,
Ainsi cu que le nombe de feuille est de n!, pour savoir la hauteur de l'arbre corresponadante (donc en terme de nombre de comparaisons) on va tomber sur log(base2) (n!)
On utilise la formule de stirling avec un tour de passe passe avec les équivalents et on trouve qu'au mieux on fera du O(nlogn)
Exemple de tri de ce type : tri fusion, tri par tas, et le tri rapide dans le cas moyen,
Faut aussi dire qu'il Existe des tril linéaire, mais qui ne se base pas uniquement sur la comparaison entre les clés mais sur une donnée supplémentaire, exemple : tri par paquets ou le tri par comptage.

Voilà, j'espère que je réponds à la question

OK pour le raisonnement, mais, est-ce que tu peux prendre un exemple avec n=3 (n!=6)? ça sera parfait!
Merci pour la réponse.

oui juska maintenant le meilleur algo de tri est en nlog(n) comme le tri rapide ou par tas,bon je crois il n'y a pas une demonstration pour ça mais je crois on est arrivé a ça en evaluant tout les algo qu'on a pu ecrire et on a trouvé que le meilleur est en nlog(n).
aprés pour calculer la complexité:
*pour les algo recursifs c'est facile:chaque appel de fonction fait k operations elementaires,la complexité depend de nombre d'appels,qu'on peut ecrire sous forme d'une suite et on resoud la suite pour trouver le terme general
*pour les algos impératifs c'est un peu plus compliqué et c'est par intuition(personnelement je fais ca)
et la complexité on n'est pa optimiste on la fixe par le pire cas
il y a des algos qui ne representent ni meilleur ni pire cas c'est pareil,comme somme d'un tableau

oui juska maintenant le meilleur algo de tri est en n.log(n) comme le tri
rapide ou par tas,bon je crois il n'y a pas une demonstration pour ça
mais je crois on est arrivé a ça en evaluant tout les algo qu'on a pu
ecrire et on a trouvé que le meilleur est en nlog(n).

A ma connaissance, il a été démontré que la meilleure complexité d'un algorithme de tri est en N.LOG(N); et ça a été prouvé mathématiquement.

Oui il y en a une preuve mathématique:
*l'operation elementaire est la comparaison de 2 elements et leur permutation si besoin :decicion
*on peut donc toujours tracer un tri comme un chemin dans un arbre
*l'arbre de decision : AB dont les feuilles sont le permutations : n!(si on compare 2 a 2)
*la hauteur de l'arbre est la complexité au pire cas
*nb feuilles d'un arbre est egale à 2^h

==>

Code:


n!<=nb feuilles<=2^h ===>  h>=log(n!) on applique la formule de Stirling sur n!(outils mathématique à ne pas demontrer ou comprendre) on obtient n.log(n)

h>=log(n!) on applique la formule de Stirling sur n!(outils
mathématique à ne pas demontrer ou comprendre)

Log(n!) = Log(1) + Log(2) + Log(3) + ... + Log(n)
Or
Log(1) <= Log(n)
Log(2) <= Log(n)
.
.
.
Log(n) <= Log(n)

donc, Log(n!) <= n.Log(n)

bien dit Nabil merci pour l'explication mon ferer <3
et propos le reste vous voyez que c'est bon?

Un lien vers des TD et des cours de Complexité Algorithmique:

http://perso.ens-lyon.fr/mathilde.noual/#ens

Lien :
http://www.nada.kth.se/~viggo/wwwcompendium/wwwcompendium.html