Publicité
+ Répondre à la discussion
Page 1 sur 2 12 DernièreDernière
Affichage des résultats 1 à 20 sur 34
  1. #1
    Membre du Club Avatar de Décembre
    Inscrit en
    avril 2010
    Messages
    228
    Détails du profil
    Informations forums :
    Inscription : avril 2010
    Messages : 228
    Points : 55
    Points
    55

    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 Confirmé Sénior

    Inscrit en
    janvier 2007
    Messages
    10 173
    Détails du profil
    Informations personnelles :
    Âge : 56

    Informations forums :
    Inscription : janvier 2007
    Messages : 10 173
    Points : 12 819
    Points
    12 819

    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 Expert
    Homme Profil pro
    Chercheur
    Inscrit en
    mars 2010
    Messages
    1 199
    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 199
    Points : 1 566
    Points
    1 566

    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 du Club Avatar de Décembre
    Inscrit en
    avril 2010
    Messages
    228
    Détails du profil
    Informations forums :
    Inscription : avril 2010
    Messages : 228
    Points : 55
    Points
    55

    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/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 081
    Points
    15 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 du Club Avatar de Décembre
    Inscrit en
    avril 2010
    Messages
    228
    Détails du profil
    Informations forums :
    Inscription : avril 2010
    Messages : 228
    Points : 55
    Points
    55

    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/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 081
    Points
    15 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 du Club Avatar de Décembre
    Inscrit en
    avril 2010
    Messages
    228
    Détails du profil
    Informations forums :
    Inscription : avril 2010
    Messages : 228
    Points : 55
    Points
    55

    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 Confirmé Sénior

    Inscrit en
    janvier 2007
    Messages
    10 173
    Détails du profil
    Informations personnelles :
    Âge : 56

    Informations forums :
    Inscription : janvier 2007
    Messages : 10 173
    Points : 12 819
    Points
    12 819

    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/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 081
    Points
    15 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 du Club Avatar de Décembre
    Inscrit en
    avril 2010
    Messages
    228
    Détails du profil
    Informations forums :
    Inscription : avril 2010
    Messages : 228
    Points : 55
    Points
    55

    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 Confirmé Sénior

    Inscrit en
    janvier 2007
    Messages
    10 173
    Détails du profil
    Informations personnelles :
    Âge : 56

    Informations forums :
    Inscription : janvier 2007
    Messages : 10 173
    Points : 12 819
    Points
    12 819

    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 du Club Avatar de Décembre
    Inscrit en
    avril 2010
    Messages
    228
    Détails du profil
    Informations forums :
    Inscription : avril 2010
    Messages : 228
    Points : 55
    Points
    55

    Par défaut

    Bonsoir et merci de m'avoir répondue

    Code :
    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 Confirmé Sénior

    Inscrit en
    janvier 2007
    Messages
    10 173
    Détails du profil
    Informations personnelles :
    Âge : 56

    Informations forums :
    Inscription : janvier 2007
    Messages : 10 173
    Points : 12 819
    Points
    12 819

    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 Expert
    Homme Profil pro
    Chercheur
    Inscrit en
    mars 2010
    Messages
    1 199
    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 199
    Points : 1 566
    Points
    1 566

    Par défaut

    Bonsoir Décembre,

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

  16. #16
    Membre Expert
    Homme Profil pro
    Chercheur
    Inscrit en
    mars 2010
    Messages
    1 199
    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 199
    Points : 1 566
    Points
    1 566

    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 du Club Avatar de Décembre
    Inscrit en
    avril 2010
    Messages
    228
    Détails du profil
    Informations forums :
    Inscription : avril 2010
    Messages : 228
    Points : 55
    Points
    55

    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 Expert
    Homme Profil pro
    Chercheur
    Inscrit en
    mars 2010
    Messages
    1 199
    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 199
    Points : 1 566
    Points
    1 566

    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 du Club Avatar de Décembre
    Inscrit en
    avril 2010
    Messages
    228
    Détails du profil
    Informations forums :
    Inscription : avril 2010
    Messages : 228
    Points : 55
    Points
    55

    Par défaut

    Merci Aleph69 ton explication est vraiment très très claire

    merci encore pour vous tous

  20. #20
    Membre du Club Avatar de Décembre
    Inscrit en
    avril 2010
    Messages
    228
    Détails du profil
    Informations forums :
    Inscription : avril 2010
    Messages : 228
    Points : 55
    Points
    55

    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

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •