Publicité
+ Répondre à la discussion
Page 2 sur 2 PremièrePremière 12
Affichage des résultats 21 à 34 sur 34
  1. #21
    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

    oui, mais je crois que Aleph t'as un peu emmêlé les pinceaux..

    (et d'ailleurs il le mentionne :
    en posant H(x)=log(G(N)), a=k, b=log(ck) et X=log(N).
    )


    là, ce que tu prouves, c'est que le log de ta fonction est proportionnel à N, donc que ta fonction est proportionnelle à l'exponentielle de N

    Si tu traces f(x) vs x, si tu mets une échelle log en X : (une échelle, hein ??)

    • si tu as une droite : ta fonction est bien en log(N)
    • si tu mets une échelle log en Y (tout en gardant l'echelle log en X), et si tu as une droite, alors c'est une loi de puissance, dont le coefficient de pente te donnera la puissance..



    PS: ta légende est fausse, puisque tu n'as pas une échelle log en x..
    "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

  2. #22
    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,
    Citation Envoyé par souviron34 Voir le message
    oui, mais je crois que Aleph t'as un peu emmêlé les pinceaux..

    (et d'ailleurs il le mentionne :

    )


    là, ce que tu prouves, c'est que le log de ta fonction est proportionnel à N, donc que ta fonction est proportionnelle à l'exponentielle de N

    Si tu traces f(x) vs x, si tu mets une échelle log en X : (une échelle, hein ??)

    • si tu as une droite : ta fonction est bien en log(N)
    • si tu mets une échelle log en Y (tout en gardant l'echelle log en X), et si tu as une droite, alors c'est une loi de puissance, dont le coefficient de pente te donnera la puissance..

    comment dois-je faire pour l'échelle? je suis perdue
    Fichiers attachés Fichiers attachés

  3. #23
    Membre Expert
    Homme Profil pro
    Chercheur
    Inscrit en
    mars 2010
    Messages
    1 197
    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 197
    Points : 1 550
    Points
    1 550

    Par défaut

    Bonjour,

    Citation Envoyé par Aleph69 Voir le message
    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.
    Mea culpa! Une erreur s'est glissée ici : il faut tracer log(T) en fonction de log(N) bien sûr!

    Tu ne dois avoir qu'un seul et unique graphique : celui de log(T) en fonction de log(N). Si tu obtiens une droite pour N grand, alors la complexité de ton algorithme est polynomiale. Sinon, il faut chercher ta loi sous une autre forme.

    Merci souviron34!

  4. #24
    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

    Citation Envoyé par Aleph69 Voir le message
    Bonjour,



    Mea culpa! Une erreur s'est glissée ici : il faut tracer log(T) en fonction de log(N) bien sûr!

    Tu ne dois avoir qu'un seul et unique graphique : celui de log(T) en fonction de log(N). Si tu obtiens une droite pour N grand, alors la complexité de ton algorithme est polynomiale. Sinon, il faut chercher ta loi sous une autre forme.

    Merci souviron34!
    Regardez ce que j'ai obtenu en traçant:

    - Log(t) en fonction de log(n)-->O(n)
    - Log(t) en fonction de log(n²)-->O(n²)
    - Log(t) en fonction de log(n^3)-->O(n^3)
    - Log(t) en fonction de log(log(n))-->O(log(n))
    - Log(t) en fonction de log(n*log(n))-->O(n*log(n))

    Il n 'ya que des lignes droites...que choisir maintenant
    Images attachées Images attachées

  5. #25
    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

    je ne sais pas ce que tu fais.. Tu n'as pas 2 fois la même échelle pour X : 10, 32, .. 4..

    Reprenons...

    De quel outil te sers-tu pour tracer ?? Avec gnuplot, il suffit de faire "set logscale x".
    "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

  6. #26
    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,

    Je trace avec matlab et les valeurs que je trace sont sur le poste #22 sous forme d'un fichier excel

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

    Par défaut

    Décembre, c'est pourtant clair :

    Citation Envoyé par Aleph69 Voir le message
    Tu ne dois avoir qu'un seul et unique graphique : celui de log(T) en fonction de log(N).

  8. #28
    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

    je ne peux l'ouvrir avec mon Excel...

    Mais maintenant, je ne connais pas Matlab, mais je suis certain qu'il y a, sns calculer quoi que ce soit, juste le moyen de modifier les échelles du tracé..
    "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

  9. #29
    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

    je ne peux l'ouvrir avec mon Excel...
    Je pense que c'est un problème d'extension essayez celui la:
    Fichiers attachés Fichiers attachés

  10. #30
    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

    si j'en crois ton premier graphique précédent, si il est bien ce qui correspond à ce que Aleph69 a dit (log(f(N)) <-> log(N)), alors :

    pour un delta de 1.85 en log(N) (entre 10.7 quand ça touche en haut et 8.85 quand ça touche en bas) , tu as un delta de 4 en log(f(N)). A vue de nez, comme ça, juste en regardant.

    C'est donc légèrement supérieur à O(N^2)... (O(N^2.16)) (puisqu'alors pour un delta de 2 en logN tu aurais 4 en log((n)))

    Pour avoir le vrai coeff, il te faut faire une régression linéaire sur ce graphique.
    "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

  11. #31
    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

    si j'en crois ton premier graphique précédent, si il est bien ce qui correspond à ce que Aleph69 a dit (log(f(N)) <-> log(N)),
    Le graphique de quel poste s'il vous plait?

  12. #32
    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

    numéro 24, juste au dessus..
    "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. #33
    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
    Je pense que c'est un problème d'extension essayez celui la:
    D'après les données de ton fichier excel, on voit bien que ta fonction "t(n)" domine n.log(n) mais est dominée par n^3.

    Et comme la courbe pour n^2 semble assez linéaire, on suspecte fortement que t(n) se comporte comme a*n^2.

    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  14. #34
    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

    Citation Envoyé par pseudocode Voir le message
    D'après les données de ton fichier excel, on voit bien que ta fonction "t(n)" domine n.log(n) mais est dominée par n^3.

    Et comme la courbe pour n^2 semble assez linéaire, on suspecte fortement que t(n) se comporte comme a*n^2.


    Merci beaucoup pour l'explication, donc il se comporte comme un a*n^2, pour le coefficient a (la pente). est ce que c'est juste de le calculer graphiquement à partir de mes données? car mon programme et très complexe et fait appel à plusieurs fonctions et c'est pas très simple de calculer la complexité directement !!

    Merci encore

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
  •