IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Mathématiques Discussion :

le terme "computational complexity"


Sujet :

Mathématiques

  1. #1
    Membre régulier Avatar de Décembre
    Inscrit en
    Avril 2010
    Messages
    277
    Détails du profil
    Informations forums :
    Inscription : Avril 2010
    Messages : 277
    Points : 110
    Points
    110
    Par défaut le terme "computational complexity"
    Bonsoir,

    J'ai écrit un programme qui traite un maillage 3D, sur ma machine j'ai effectuer quelques tests avec différents maillages 3D (je changeais à chaque fois le nombre de cellule du maillage) et j'ai noté à chaque fois le temps d’exécution ce qui m'a permis de tracer la figure ci-jointe avec Excel.

    J'ai vu sur certain document le terme "computational complexity" et mes recherche m'ont aidées à comprendre que ce terme ne veut pas dire temps d’exécution, pouvez vous m'éclairer s'il vous plait?

    merci
    Images attachées Images attachées  

  2. #2
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    De manière générale c'est la définition du comportement de l'algo en foncton de la taille de l'entrée..

    Elle est souvent calculée - et est représentative - comme le "noeud", c'est à dire la plus grosse partie de l'algo..

    Par exemple une boucle simple sur N éléments sera dite O'N). Une double boucle sur N et M éléments (une matrice) sera O(N*M). On néglige les facteurs constants : quand on dit "un algo est en O(N^2), on dit que c'est "proportionnel au carré de l'entrée"..

    Il faut donc analyser chaque partie de ton algo et en tirer la partie donnant la plus grosse dépendance : c'est ce qui limitera..

    Bien entendu, il peut y avoir plusieurs types de complexités. Regarde Wiki..

    La plus courante est celle que j'ai indiquée...
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  3. #3
    Membre expérimenté
    Homme Profil pro
    Chercheur
    Inscrit en
    Mars 2010
    Messages
    1 218
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : Mars 2010
    Messages : 1 218
    Points : 1 685
    Points
    1 685
    Par défaut
    Bonjour,

    la complexité (temporelle) d'un algorithme correspond au nombre d'opérations effectuées en fonction des données. Il s'agit donc d'une mesure de performance comme l'est le temps d'exécution. La différence essentielle entre les deux notions est que le temps d'exécution d'un algorithme pourra varier selon l'architecture : les calculateurs sont de plus en plus performants et les temps d'exécution tendent à diminuer. Ce n'est pas le cas de la complexité qui, en ce sens, est une meilleure mesure de performance que le temps d'exécution.

  4. #4
    Membre régulier Avatar de Décembre
    Inscrit en
    Avril 2010
    Messages
    277
    Détails du profil
    Informations forums :
    Inscription : Avril 2010
    Messages : 277
    Points : 110
    Points
    110
    Par défaut
    Salut et merci pour vos réponses

    Grace à vous j'ai trouver un document qui parle de "comutational complexity" mais il cite différents ordres:

    O(1) constant
    O(loga n) logarithmic
    O(n) linear
    O(n loga n) \n log n"
    O(n2) quadratic
    O(n3) cubic
    O(nr) polynomial
    O(an) exponential
    O(n!) factorial
    Comment peut-on savoir quel cas de figure est le notre (je parle de la liste d'ordre ci-dessus)

    merci

  5. #5
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par Décembre Voir le message
    Comment peut-on savoir quel cas de figure est le notre (je parle de la liste d'ordre ci-dessus)
    Puisque tu as les valeurs mesurées pour ton algo, le plus simple c'est de tracer la courbe suivant chaque échelle (n, n^2, log(n), ...) et regarder laquelle donne une ligne droite.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  6. #6
    Membre régulier Avatar de Décembre
    Inscrit en
    Avril 2010
    Messages
    277
    Détails du profil
    Informations forums :
    Inscription : Avril 2010
    Messages : 277
    Points : 110
    Points
    110
    Par défaut
    Salut,

    Puisque tu as les valeurs mesurées pour ton algo, le plus simple c'est de tracer la courbe suivant chaque échelle (n, n^2, log(n), ...) et regarder laquelle donne une ligne droite.
    C-à-d je prends les valeurs (que j'ai mise sur l'axe des x) sur la figure que j'ai joint à mon premier message et j'essaie de trouver laquelle se rapproche le plus d'elle?

  7. #7
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par Décembre Voir le message
    C-à-d je prends les valeurs (que j'ai mise sur l'axe des x) sur la figure que j'ai joint à mon premier message et j'essaie de trouver laquelle se rapproche le plus d'elle?
    Chaque point de mesure Pi a pour coordonnées un couple de valeur (Xi,Yi).

    Il te suffit de tracer les nuages de points suivants:
    * nuage des points (Xi,Yi)
    * nuage des points (log(Xi),Yi)
    * nuage des points (Xi^2,Yi)
    ...

    Le nuage de point qui forme une ligne t'indiquera le type de complexité.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  8. #8
    Membre régulier Avatar de Décembre
    Inscrit en
    Avril 2010
    Messages
    277
    Détails du profil
    Informations forums :
    Inscription : Avril 2010
    Messages : 277
    Points : 110
    Points
    110
    Par défaut

    Le nuage de point qui forme une ligne t'indiquera le type de complexité
    Excusez mon ignorance, mais pourquoi devrais-je chercher une ligne?

    merci

  9. #9
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    parce que avec une corrélation linéaire tu as un coefficient de corrélation... Ce qui n'est pas directement atteignable avec des fits divers ou variés : tout ce que tu pourras avoir c'est des écarts relatifs, et tu pourrais mentionner le max..

    Dans le cas d'un fit linéaire, le coefficient de corrélation est une mesure reconnue par tout le monde : un coefficient de confiance..

    Si c'est linéaire, y'a pas de problèmes.
    Si c'est expoentiel, ça devient plus compliqué.. Une superposition de courbe ferait illusion, mais ne donnerait pas d'indications précises.

    Donc, si ton algo se comporte en O(N^2), si tu prends le log, tu devrais avoir une droite de pente 2.
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  10. #10
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par Décembre Voir le message
    Excusez mon ignorance, mais pourquoi devrais-je chercher une ligne?
    Souviron34 à très bien expliqué la raison.

    Pour faire simple, si tu as une complexité en N^2 alors les points Pi forment visuellement une parabole. Pi = (Xi,Yi) ~= (Xi, a.Xi^2)

    Comme visuellement c'est dur de reconnaitre une parabole, il est plus pratique de changer l'échelle sur l'axe X --> Qi = (Xi^2,Yi) ~= (Xi^2, a.Xi^2)

    Dans ce cas, les points Qi forment visuellement une droite. C'est plus facile a reconnaitre.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  11. #11
    Membre régulier Avatar de Décembre
    Inscrit en
    Avril 2010
    Messages
    277
    Détails du profil
    Informations forums :
    Inscription : Avril 2010
    Messages : 277
    Points : 110
    Points
    110
    Par défaut
    Salut et merci pour votre aide

    Comme vous pouvez le constater sur la figure jointe, je n'ai pas obtenu de ligne droite en traçant les différente fonction

    Que dois-je faire d'après vous ?

    merci
    Images attachées Images attachées  

  12. #12
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par Décembre Voir le message
    Que dois-je faire d'après vous ?
    D'une part avoir plus de points de mesure...

    Là, d'après ce qu'on peut voir, ça semblerait en O(N^2)...

    Ce qui serait pas mal pour un maillage 3D, et normal pour un 2D.

    Ensuite, analyser plus propement ton algorithme, comme je l'ai expliqué dans la discussion Etude de complexité de l'implémentation d'un algorithme donné, en particulier au post #10
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  13. #13
    Membre régulier Avatar de Décembre
    Inscrit en
    Avril 2010
    Messages
    277
    Détails du profil
    Informations forums :
    Inscription : Avril 2010
    Messages : 277
    Points : 110
    Points
    110
    Par défaut
    Bonsoir et merci de m'avoir répondue

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
     
    Là, d'après ce qu'on peut voir, ça semblerait en O(N^2)...
    ça ne ressemblerai pas à un O(nlog(n))?
    merci d'avance

  14. #14
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par Décembre Voir le message
    ça ne ressemblerai pas à un O(nlog(n))?
    Avec aussi peu de points difficile à dire, mais ça n'a pas l'air.. : ça a l'air de démarrer plat puis de monter..

    Alors que la courbe en N^2 a l'air plus droite..
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  15. #15
    Membre expérimenté
    Homme Profil pro
    Chercheur
    Inscrit en
    Mars 2010
    Messages
    1 218
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : Mars 2010
    Messages : 1 218
    Points : 1 685
    Points
    1 685
    Par défaut
    Bonsoir Décembre,

    peux-tu nous donner les grandes étapes de ton algorithme?

  16. #16
    Membre expérimenté
    Homme Profil pro
    Chercheur
    Inscrit en
    Mars 2010
    Messages
    1 218
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : Mars 2010
    Messages : 1 218
    Points : 1 685
    Points
    1 685
    Par défaut
    Citation Envoyé par Décembre Voir le message
    ça ne ressemblerai pas à un O(nlog(n))?
    Bien que je ne cautionne pas l'approche adoptée, je pense que tu auras une meilleure idée du comportement de ton algorithme en ayant plus de points de mesure. Idéalement, il faudrait une trentaine de points de mesure à égale distance les uns des autres en abscisse (grossièrement bien sûr) et pour des grandes valeurs de n (ce que tu fais déjà) puisqu'on souhaite uniquement une tendance asymptotique. Il se peut que, pour une raison à déterminer, tu sois en présence de valeurs aberrantes bruitant trop fortement ton problème de régression (à cause du faible nombre de points).

    EDIT : conserve les points de mesure dans une table que tu pourras poster afin que chacun puisse t'aider à trouver l'équation mystère...

  17. #17
    Membre régulier Avatar de Décembre
    Inscrit en
    Avril 2010
    Messages
    277
    Détails du profil
    Informations forums :
    Inscription : Avril 2010
    Messages : 277
    Points : 110
    Points
    110
    Par défaut
    Bonsoir,

    J'ai pris plus de valeur comme vous me l'aviez recommandé et vous avez raison la ligne droite se confirme pour le O(n²).

    J'ai lu certain document mais j'avoue que je n'arrive toujours pas à comprendre comment et pourquoi on obtient une ligne droite à la complexité temporelle de l'algorithme?
    Images attachées Images attachées  

  18. #18
    Membre expérimenté
    Homme Profil pro
    Chercheur
    Inscrit en
    Mars 2010
    Messages
    1 218
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : Mars 2010
    Messages : 1 218
    Points : 1 685
    Points
    1 685
    Par défaut
    Bonsoir,

    Citation Envoyé par Décembre Voir le message
    J'ai lu certain document mais j'avoue que je n'arrive toujours pas à comprendre comment et pourquoi on obtient une ligne droite à la complexité temporelle de l'algorithme?
    C'est très simple. Ce que tu cherches est la loi F liant le temps d'exécution T à la taille N des données :
    T=F(N)
    Tu es face à un problème de régression. L'idée la plus naturelle consiste à chercher F sous la forme d'un polynôme d'un certain degré k (inconnu) :
    F(N)=c0+c1*N+c2*N²+...+ck*N^k,
    où c0,...,ck sont des coefficients réels (inconnus).
    Lorsque que N grandit (tend vers l'infini), le terme de plus haut degré, c'est-à-dire ck*N^k, grandit plus vite que les autres termes et finit par devenir tellement grand par rapport aux autres que les valeurs de F(N) et ck*N^k sont presque les mêmes. En d'autres termes, la somme
    F(N)-ck*N^k = c0+c1*N+c2*N²+...+c_{k-1}*N^{k-1}
    joue un rôle mineur dans l'évaluation de F(N). Mathématiquement, il suffit de diviser F(N) par ck*N^k pour le voir, puisque le membre de droite dans
    F(N)/(ck*N^k) = c0/N^k + c1/N^{k-1}+...+c_{k-1}/N+1
    tend vers 1 quand N tend vers l'infini. Pour signifier cela de façon synthétique, on utilise la notation de Landau
    F(N)=O(N^k)
    Bref, en prenant N suffisamment grand, on peut identifier F(N) à la fonction G(N)=ck*N^k en commettant une erreur d'approximation très petite. Le problème ici est maintenant d'identifier le degré k (et éventuellement le coefficient ck). Visuellement, il est très difficile de différencier des puissance entre elles comme tu as pu le constater. Pour faciliter cette étape, et dans le cas particulier d'une puissance, on regarde plutôt le logarithme car
    log(G(N))=log(ck*N^k)=log(ck)+log(N^k)=log(ck)+k*log(N)
    est l'équation d'une droite que l'on peut écrire plus simplement sous la forme
    H(x)=a*x+b
    en posant H(x)=log(G(N)), a=k, b=log(ck) et X=log(N). Concrètement, il te suffit donc de faire des mesures (N,T) pour N assez grand, puis de tracer, non pas T en fonction de N, mais log(T) en fonction N. Si la relation entre N et T est polynomiale, alors tu obtiendras (aux erreurs de mesure près) une droite de coefficient directeur le degré k de ton polynôme et d'ordonnée à l'origine le logarithme log(ck) du coefficient ck associé au terme prépondérant N^k. Hormis une analyse sur papier de ton algorithme pour déterminer exactement sa complexité (même pour N petit), la meilleure façon d'estimer la pente a et l'ordonnée à l'origine b de ta droite est la méthode statistique appelée régression linéaire.

    J'espère que tout est clair.

    Pense bien à passer ce sujet en résolu et bon courage pour la suite.

  19. #19
    Membre régulier Avatar de Décembre
    Inscrit en
    Avril 2010
    Messages
    277
    Détails du profil
    Informations forums :
    Inscription : Avril 2010
    Messages : 277
    Points : 110
    Points
    110
    Par défaut
    Merci Aleph69 ton explication est vraiment très très claire

    merci encore pour vous tous

  20. #20
    Membre régulier Avatar de Décembre
    Inscrit en
    Avril 2010
    Messages
    277
    Détails du profil
    Informations forums :
    Inscription : Avril 2010
    Messages : 277
    Points : 110
    Points
    110
    Par défaut
    puis de tracer, non pas T en fonction de N, mais log(T) en fonction N.
    ça change tout !! regardez l'image jointe avec log(t) en fonction des n la complexité à l'air d'être log(n)
    Images attachées Images attachées  

Discussions similaires

  1. Quote et double quote
    Par aktos dans le forum Langage
    Réponses: 8
    Dernier message: 05/01/2007, 20h55

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo