Forum INFOMATH
Vous souhaitez réagir à ce message ? Créez un compte en quelques clics ou connectez-vous pour continuer.
-50%
Le deal à ne pas rater :
-50% sur les sacs à dos pour ordinateur portable Urban Factory ...
19.99 € 39.99 €
Voir le deal

complexité algorithmique

+2
algoghost
Lamice
6 participants

Aller en bas

complexité algorithmique Empty complexité algorithmique

Message par Invité Jeu 27 Aoû - 0:31

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!

Invité
Invité


Revenir en haut Aller en bas

complexité algorithmique Empty Re: complexité algorithmique

Message par Lamice Jeu 27 Aoû - 11:42

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

Féminin
Nombre de messages : 74
Age : 35
Localisation : ENIM
Réputation : 3
Points : 5798
Date d'inscription : 18/06/2008

Feuille de personnage
Capacité linguistique:
complexité algorithmique Left_bar_bleue1000/1000complexité algorithmique Empty_bar_bleue  (1000/1000)

http://ipeilamice.clicforum.com

Revenir en haut Aller en bas

complexité algorithmique Empty Re: complexité algorithmique

Message par Invité Ven 28 Aoû - 0:06

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+

Invité
Invité


Revenir en haut Aller en bas

complexité algorithmique Empty Re: complexité algorithmique

Message par algoghost Mar 24 Nov - 17:07

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!!

algoghost
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 20
Localisation : France
Réputation : 7
Points : 5303
Date d'inscription : 18/11/2009

Revenir en haut Aller en bas

complexité algorithmique Empty Re: complexité algorithmique

Message par methodiX Jeu 26 Nov - 23:02

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

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 7014
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
complexité algorithmique Left_bar_bleue1000/1000complexité algorithmique Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

complexité algorithmique Empty Re: complexité algorithmique

Message par algoghost Ven 27 Nov - 6:20

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

algoghost
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 20
Localisation : France
Réputation : 7
Points : 5303
Date d'inscription : 18/11/2009

Revenir en haut Aller en bas

complexité algorithmique Empty Re: complexité algorithmique

Message par methodiX Ven 27 Nov - 15:14

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.
methodiX
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 7014
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
complexité algorithmique Left_bar_bleue1000/1000complexité algorithmique Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

complexité algorithmique Empty Re: complexité algorithmique

Message par moudhafer Jeu 27 Mai - 3:32

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 Sad
il y a des algos qui ne representent ni meilleur ni pire cas c'est pareil,comme somme d'un tableau
Smile

moudhafer
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 58
Age : 35
Localisation : france
Réputation : 0
Points : 5124
Date d'inscription : 26/05/2010

Revenir en haut Aller en bas

complexité algorithmique Empty Re: complexité algorithmique

Message par informix Jeu 27 Mai - 21:48

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.
informix
informix
Nombre Rationnel
Nombre Rationnel

Nombre de messages : 399
Réputation : 4
Points : 6286
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
complexité algorithmique Left_bar_bleue1000/1000complexité algorithmique Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

complexité algorithmique Empty Re: complexité algorithmique

Message par moudhafer Mar 15 Juin - 3:25

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)

moudhafer
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 58
Age : 35
Localisation : france
Réputation : 0
Points : 5124
Date d'inscription : 26/05/2010

Revenir en haut Aller en bas

complexité algorithmique Empty Re: complexité algorithmique

Message par Napoléon Mer 16 Juin - 1:13

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)
Napoléon
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7632
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
complexité algorithmique Left_bar_bleue999/1000complexité algorithmique Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

complexité algorithmique Empty Re: complexité algorithmique

Message par moudhafer Mar 22 Juin - 15:43

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

moudhafer
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 58
Age : 35
Localisation : france
Réputation : 0
Points : 5124
Date d'inscription : 26/05/2010

Revenir en haut Aller en bas

complexité algorithmique Empty Re: complexité algorithmique

Message par methodiX Ven 9 Juil - 12:56

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

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

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 7014
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
complexité algorithmique Left_bar_bleue1000/1000complexité algorithmique Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

complexité algorithmique Empty Re: complexité algorithmique

Message par methodiX Ven 9 Juil - 16:28

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

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 7014
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
complexité algorithmique Left_bar_bleue1000/1000complexité algorithmique Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

complexité algorithmique Empty Re: complexité algorithmique

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum